- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies stochastic Lipschitz bandits on when the learner is subject to two simultaneous constraints - at most batches and bits of memory. For of order , it pins down the minimax regret up to log factors. The rate is the maximum of three terms: the usual , the batch-depth term , and a new joint term . It also shows that with a single bit of memory, adaptive batch boundaries give regret of order , 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 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 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 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 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 ( in the paper's own 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
- It gives a tight minimax characterization, up to log factors, of Lipschitz bandits under joint memory and batch constraints for .
- Lower and upper bounds match across all three regimes.
- The two-scale idea is clean. Memory only pays for the coarse regional choice, and fine search inside near-optimal cells costs regret per pull. This beats a naive grid reduction by a polynomial factor in the joint regime.
- The one-bit result separating adaptive from fixed batch boundaries is a nice addition.
- The proofs are careful. The appendix tracks memory use, batch counts and horizon constraints explicitly.
Critical weaknesses
- 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.
- 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 . The matching lower bound may also follow from embedding their hard instance as bumps.
- The gain over the naive reduction is confined to the joint regime and is modest. The paper's own example improves by .
- Both earlier Lipschitz papers adapt to the zooming dimension. These results only cover the worst case over the full Lipschitz class.
- The regime is left open, so the characterization is incomplete exactly where memory is most constrained.
- 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
- 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.
- 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 example.
- Do the techniques extend to zooming-dimension bounds? Even a remark on the obstacles would help.
- 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.
- 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.