Memory--Batch Tradeoffs in Lipschitz Bandits

Abstract:Lipschitz bandits admit near-optimal regret $\widetilde O_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^{\frac{d+2}{d+3}} (1+(B-1)W)^{-\frac{1}{d(d+3)}}$. When $W\gtrsim_d\log(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 $\widetilde O_d(T^{(d+1)/(d+2)})$ regret requires both $B=\Omega_d(\log\log T)$ and $(B-1)W=\widetilde{\Omega}_d(T^{d/(d+2)})$. With one bit of memory, minimax regret is $\widetilde\Theta_d(TB^{-1/(d+2)})$ under adaptive batch boundaries while $\Theta_d(T)$ under fixed boundaries.

Machine Learning (cs.LG); Machine Learning (stat.ML)

arXiv:2608.07922 [cs.LG]

(or arXiv:2608.07922v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2608.07922 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.