Memory--Batch Tradeoffs in Lipschitz Bandits

Abstract

Lipschitz bandits admit near-optimal regret ${\tilde{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 ${\tilde{O}}_d(T^{(d+1)/(d+2)})$ regret requires both $B={\Omega }_d(\log \log T)$ and $(B-1)W={\tilde{\Omega }}_d(T^{d/(d+2)})$. With one bit of memory, minimax regret is ${\tilde{\Theta }}_d(T{B}^{-1/(d+2)})$ under adaptive batch boundaries while ${\Theta }_d(T)$ under fixed boundaries.