Memory-Batch Tradeoffs in Adaptive Lipschitz Bandits

Adaptive learning systems, such as stochastic Lipschitz bandits, require a balance between maintaining a memory of past observations and acting on that information. This study investigates the intricate "width-depth" tradeoff, specifically how the amount of retained reward-dependent state (memory width, W) interacts with the number of committed action batches (update depth, B). The researchers characterized the minimax expected pseudo-regret, a measure of performance, under various memory and batch constraints. Their findings introduce a new penalty term, demonstrating mathematically that memory width and update depth are not interchangeable. This interaction stems from an information-routing constraint: achieving low regret necessitates encoding a significant number of regional decisions within the action transcript, while the available memory for boundary states is limited by the product of batch count and memory width. The study proposes matching policies that manage this constraint by streaming and erasing verification statistics while maintaining a mask of a safe active set. These policies can operate either by retaining information in memory or by processing it in fragments. The theoretical framework successfully recovers known results for both fully sequential learning and batch-only scenarios, showing that even static batch boundaries can align with predictable adaptive ones.