Memory--Batch Tradeoffs in Lipschitz Bandits
Abstract
Lipschitz bandits admit near-optimal regret Õd(T(d+1)/(d+2)) with little memory under full adaptivity, or with few batches under unrestricted memory. We characterize the minimax expected pseudo-regret over T rounds with W bits of memory and at most B batches in dimension d. For every memory budget W, we prove a lower bound of order T(d+2)/(d+3) (1+(B−1)W)−1/(d(d+3)). When W≳dlog(eT), algorithms with fixed batch boundaries attain, up to logarithmic factors, the larger of this bound and the optimal B-batch regret with unrestricted memory. The analysis separates fine-scale comparisons from the regional information needed to allocate their samples at low regret. Attaining Õd(T(d+1)/(d+2)) regret requires both B=Ωd(loglog T) and (B−1)W=Ω̃d(Td/(d+2)). With one bit of memory, minimax regret is Θ̃d(TB−1/(d+2)) under adaptive batch boundaries while Θd(T) under fixed boundaries.
Related
- Energy-performance tradeoffs in server farms with batch services and setup times
- The Right to Be Forgotten under Correlation: Privacy-Utility Tradeoffs
- Exact Storage-Repair-Bandwidth Tradeoffs for (6,5,5) and (7,6,6) Exact-Repair Regenerating Codes
- Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs
- Diffusion Sensitivity Geometry and Strong Duality for Optimal Privacy-Utility Tradeoffs
BibTeX
@misc{lyu2026memorybatch,
title = {{Memory--Batch Tradeoffs in Lipschitz Bandits}},
author = {Zicheng Lyu and Zengfeng Huang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.07922},
eprint = {2608.07922},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.07922},
}
RIS
TY - UNPB
TI - Memory--Batch Tradeoffs in Lipschitz Bandits
AU - Zicheng Lyu
AU - Zengfeng Huang
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2608.07922
UR - https://arxiv.org/abs/2608.07922
AB - Lipschitz bandits admit near-optimal regret Õ_d(T^(d+1)/(d+2)) with little memory under full adaptivity, or with few batches under unrestricted memory. We characterize the minimax expected pseudo-regret over T rounds with W bits of memory and at most B batches in dimension d. For every memory budget W, we prove a lower bound of order T^(d+2)/(d+3) (1+(B−1)W)^−1/(d(d+3)). When W≳_dlog(eT), algorithms with fixed batch boundaries attain, up to logarithmic factors, the larger of this bound and the optimal B-batch regret with unrestricted memory. The analysis separates fine-scale comparisons from the regional information needed to allocate their samples at low regret. Attaining Õ_d(T^(d+1)/(d+2)) regret requires both B=Ω_d(loglog T) and (B−1)W=Ω̃_d(T^d/(d+2)). With one bit of memory, minimax regret is Θ̃_d(TB^−1/(d+2)) under adaptive batch boundaries while Θ_d(T) under fixed boundaries.
ER -