Information Routing across Batch Boundaries: Memory--Batch Tradeoffs in Lipschitz Bandits

arXiv:2608.07922v1 Announce Type: new Abstract: Adaptive learning needs both a state that preserves what observations imply and opportunities to act on that state. We study this width--depth tradeoff in stochastic Lipschitz bandits. After each pull, the learner retains at most W bits of live reward-dependent state and organizes its pulls into at most B committed batches. For Wgtrsim_dlog(eT), we characterize minimax expected pseudo-regret up to logarithmic factors; the lower bounds hold for every W. Besides the classical sequential and unrestricted-memory batch costs, the frontier contains the new penalty [ T^{frac{d+2}{d+3}} igl(1+(B-1)Wigr)^{-frac1{d(d+3)}}, ] proving that state width and update depth are not interchangeable. The interaction is an information-routing constraint: at regional scale s, low regret forces the committed action transcript to encode Theta_d(s^{-d}) regional decisions, while the collected boundary states carry at most (B-1)W bits of entropy. Matching policies stream and erase verification statistics while retaining a mask of a safe active set, either in memory or fragment by fragment. The theorem recovers the full-dimensional worst-case batch-only frontier and logarithmic-memory achievability in the fully sequential specialization; static batch boundaries match predictable adaptive ones.

Source: arXiv cs.LG | 2026-08-11