acceptodds
Under review as a conference paper at ICLR 2027

Memory-Batch Trade-offs in Lipschitz Bandits

Abstract

Lipschitz bandits admit near-optimal regret with little memory under full adaptivity, or with few batches under unrestricted memory. We characterize the minimax expected pseudo-regret over rounds with bits of memory and at most batches in dimension . For every memory budget , we prove a lower bound of order . When , algorithms with fixed batch boundaries attain, up to logarithmic factors, the larger of this bound and the optimal -batch regret with unrestricted memory. The analysis separates fine-scale comparisons from the regional information needed to allocate their samples at low regret. Attaining regret requires both and . With one bit of memory, minimax regret is under adaptive batch boundaries while under fixed boundaries.

Primary area:
learning theory
Keywords:
Learning theory, Lipschitz bandits, finite memory, batched adaptivity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_pm4QOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies stochastic Lipschitz bandits on [0,1]d[0,1]^d when the learner is subject to two simultaneous constraints - at most BB batches and WW bits of memory. For WW of order log⁡T\log T, it pins down the minimax regret up to log factors. The rate is the maximum of three terms: the usual T(d+1)/(d+2)T^{(d+1)/(d+2)}, the batch-depth term Tβ/B2T^{\beta}/B^2, and a new joint term T(d+2)/(d+3)(1+(B−1)W)−1/(d(d+3))T^{(d+2)/(d+3)}(1+(B−1)W)^{-1/(d(d+3))}. It also shows that with a single bit of memory, adaptive batch boundaries give regret of order T⋅B−1/(d+2)T\cdot B^{-1/(d+2)}, while fixed boundaries force linear regret. The work sits on three recent papers. Feng, Huang & Wang (NeurIPS 2022; IEEE TIT 2024) handle batched Lipschitz bandits with unlimited memory. Zhu & Huang (ICLR 2025) handle fully sequential Lipschitz bandits with log⁡T\log T bits. Huang, Lyu, Zhu & Huang (arXiv 2026) treat the joint constraint for K-armed bandits. This submission is essentially the Lipschitz version of that last paper. It reuses its policy model, the argument that boundary states carry at most (B−1)W(B−1)W bits, and the localized change of measure. The batch-depth lower bound comes from Feng et al. The algorithms combine group-wise elimination and a stored reference arm (Roy Chaudhuri and Kalyanakrishnan; Liau et al.) with BLiN-style hierarchical refinement. The genuinely new idea is the two-scale argument. Only the coarse choice of region has to be paid for in memory. Fine search inside near-optimal cells costs only O(s)O(s) regret per pull, so it can run with logarithmic state. That idea drives both the joint upper bound and the matching lower bound.

The analysis is careful and, as far as I can tell, correct. The two-scale construction is a nice observation and does beat a naive grid reduction. My main concern is significance. The practical takeaway i.e. that near optimal regret with W bits needs roughly Td/(d+2)/WT^{d/(d+2)}/W batches, seems mostly implied by earlier work. Running Huang et al.'s algorithm on a grid already achieves it. I'd like the authors to explain whether the lower-bound side also follows from Huang et al. applied to bump instances. If it does, the new content reduces to the joint term. That term improves on the naive bound only in an intermediate regime, and by modest polynomial factors (T1/16T^{1/16} in the paper's own d=1d = 1 example). The results also lose the zooming dimension adaptivity that both earlier Lipschitz papers have. The sub-logarithmic memory regime is left open. The one-bit separation is interesting, but it largely comes from storing information in batch lengths, which says more about the model than about the problem. Overall this is a solid but incremental extension of the authors' K-armed result, and I lean toward a weak reject.

Critical strengths
  1. It gives a tight minimax characterization, up to log factors, of Lipschitz bandits under joint memory and batch constraints for W>log⁡TW > \log T.
  2. Lower and upper bounds match across all three regimes.
  3. The two-scale idea is clean. Memory only pays for the coarse regional choice, and fine search inside near-optimal cells costs O(s)O(s) regret per pull. This beats a naive grid reduction by a polynomial factor in the joint regime.
  4. The one-bit result separating adaptive from fixed batch boundaries is a nice addition.
  5. The proofs are careful. The appendix tracks memory use, batch counts and horizon constraints explicitly.
Critical weaknesses
  1. Limited novelty relative to Huang et al. (2026). The policy model, the boundary-state information bound, the change-of-measure lemma and the group-wise elimination are all carried over. The batch-depth term is imported from Feng et al.
  2. The headline batch-complexity corollary seems largely implied by prior work. Running Huang et al.'s algorithm on a grid already gets near-optimal regret once BW>Td/(d+2)BW > T^{d/(d+2)}. The matching lower bound may also follow from embedding their hard instance as bumps.
  3. The gain over the naive reduction is confined to the joint regime and is modest. The paper's own d=1d = 1 example improves by T1/16T^{1/16}.
  4. Both earlier Lipschitz papers adapt to the zooming dimension. These results only cover the worst case over the full Lipschitz class.
  5. The 2≤W=o(log⁡T)2 \leq W = o(\log T) regime is left open, so the characterization is incomplete exactly where memory is most constrained.
  6. The one-bit upper bound works by encoding information in batch lengths through the free round counter. That reflects how the model is set up more than how hard the problem is.
Questions for authors
  1. Can Corollary 3.2, both directions, be derived directly from Huang et al. (2026) applied to a grid of Lipschitz bumps? If yes, please say so explicitly and position the joint term as the main contribution. If no, explain what fails.
  2. Please describe more clearly the regimes where the joint term strictly improves on the direct-grid bound, and how large the improvement is beyond the single d=1d = 1 example.
  3. Do the techniques extend to zooming-dimension bounds? Even a remark on the obstacles would help.
  4. In the one-bit result, adaptive boundaries effectively provide extra memory through the round index. Would a model that charges for that information change the conclusions? This deserves a short discussion in the main text.
  5. Please separate more clearly what is new from what is reused. The related work section touches on this, but a short explicit list would make the contribution easier to judge.
Reviewer_6d1QOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies stochastic Lipschitz bandits under simultaneous memory and batch constraints. The learner selects actions from [0,1]d[0,1]^d, where the unknown expected reward function is one-Lipschitz, while retaining at most WW bits of reward-dependent mutable state and using at most BB batches. Within each batch, observations may update the stored state but cannot change the prescribed actions or batch boundary.

For W≥Cdlog⁡(eT)W\ge C_d\log(eT), the authors characterize the minimax expected pseudo-regret up to logarithmic factors as

T^{\frac{d+1}{d+2}} \vee \frac{T^{\beta_{d,B}}}{B^2} \vee T^{\frac{d+2}{d+3}} [1+(B-1)W]^{-\frac{1}{d(d+3)}} \right),$$ where $\beta_{d,B}=(d+1)/((d+2)[1-(d+2)^{-B}])$. These terms capture statistical uncertainty, limited batches, and the joint memory–batch restriction. The upper bounds use fixed batch boundaries and separate coarse regional selection from fine action comparisons. The paper also studies one-bit memory. With adaptive batch boundaries, the minimax regret is $\widetilde\Theta_d(TB^{-1/(d+2)})$, whereas fixed boundaries incur linear regret. The adaptive construction encodes information in batch timing and recovers it through the freely available round and batch indices.
Critical strengths
  1. The paper provides a meaningful characterization of the interaction between memory and batch constraints. The nearly matching upper and lower bounds identify an additional regret term that cannot be explained by either restriction alone. In particular, logarithmic memory requires polynomially many batches to achieve near-optimal regret, even though only Od(log⁡log⁡T)O_d(\log\log T) batches are sufficient with unrestricted memory. This gives a clear theoretical explanation of the cost of imposing both resource constraints.

  2. The lower-bound construction is technically interesting and provides useful intuition. The hard instances contain pairs of coarse cells, with one optimal cell in each pair and smaller local improvements hidden within the optimal cells. Achieving low regret requires testing these local alternatives while avoiding excessive sampling of the suboptimal cells. Consequently, the action allocation reveals information about the hidden regional choices. Comparing this information requirement with the (B−1)W(B-1)W bits carried by boundary states yields the joint lower bound.

  3. The one-bit result reveals an interesting distinction between fixed and adaptive batch boundaries. Under the stated memory model, adaptive boundaries permit sublinear regret with one mutable bit, while fixed boundaries incur linear regret regardless of the batch budget. The analysis also goes beyond the general boundary-state information bound by controlling how well a two-state process distinguishes local alternatives, uniformly over batch length. This result clarifies how batch timing can affect the power of memory-constrained policies.

Critical weaknesses
  1. The minimax characterization remains incomplete for memory budgets between one bit and logarithmic memory. The main matching result requires W≥Cdlog⁡(eT)W\ge C_d\log(eT), while the additional theorem addresses W=1W=1. The sharp dependence for 2≤W=o(log⁡T)2\le W=o(\log T) remains unresolved. This is a meaningful gap because the general three-term lower bound can be polynomially loose below logarithmic memory. For example, when d=1d=1, B≍T1/2B\asymp T^{1/2}, and W=1W=1, that bound gives order T2/3T^{2/3}, whereas the one-bit result gives Θ~(T5/6)\widetilde\Theta(T^{5/6}). Although the authors acknowledge this limitation, it leaves the transition between the two characterized regimes unclear.

  2. The guarantees concern the full Lipschitz class and depend on the ambient dimension dd, rather than adapting to the complexity of the near-optimal region. In problems where only a small part of the domain is competitive, the worst-case guarantees may not describe the attainable regret or resource requirements. Since adapting to near-optimal-region geometry is an important aspect of Lipschitz bandits, it would be useful to understand whether the proposed memory–batch tradeoff can be refined using zooming dimension or another instance-dependent measure.

Questions for authors
  1. What upper and lower bounds can be obtained for 2≤W=o(log⁡T)2\le W=o(\log T)? Can the one-bit lower-bound argument be extended to policies with more states, and how does additional memory improve the dependence on the batch budget?

  2. Can the two-scale construction be adapted to obtain guarantees depending on zooming dimension or another measure of near-optimal-region complexity? What are the main obstacles to extending the joint lower and upper bounds to such settings?

Reviewer_t6rsOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies stochastic Lipschitz bandits under simultaneous restrictions on memory and adaptivity. For W≥log⁡TW \geq \log T, it characterizes minimax regret up to logarithmic factors as the maximum of the sequential statistical term, the unrestricted-memory batching term, and a new interaction term Td+2d+3(1+(B−1)W)−1d(d+3)T^{\frac{d+2}{d+3}} \bigl(1+(B-1)W\bigr)^{-\frac{1}{d(d+3)}}. The central idea separates the information needed to identify promising coarse regions from the sampling needed to compare actions at a finer resolution. The paper also establishes a sharp qualitative separation for one-bit memory: adaptive batch boundaries permit sublinear regret when the batch budget grows sufficiently, whereas fixed boundaries incur linear regret.

Critical strengths
  • The paper gives a substantial theoretical result.
  • The paper seems mathematically sound and I did not find any errors.
  • The one-bit result exposes the role of timing information in memory-constrained learning.
Critical weaknesses
  • The presentation makes the contributions somewhat hard to absorb. The main text introduces several constructions and parameter regimes. I would suggest the authors include the one-dimensional example in Appendix D.4 in the main text.
  • It seems that the strongest contribution of the paper is the Lipschitz regret characterization. I would appreciate a more explicit explanation of which technical obstacle prevents the earlier analysis from yielding this characterization directly.
Questions for authors
  • Could the authors explain which part of the main characterization requires the new geometric argument beyond the finite-arm framework?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.