🤖 machine learning

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

This paper characterizes the minimax expected pseudo-regret in stochastic Lipschitz bandits under simultaneous constraints on memory width ( $W$ ) and batch depth ( $B$ ), revealing a fundamental information-routing tradeoff where these parameters are non-interchangeable and jointly determine a new regret frontier of $T^{\frac{d+2}{d+3}} (1+(B-1)W)^{-\frac1{d(d+3)}}$ .

Original authors: Zicheng Lyu, Zengfeng Huang

Published 2026-08-11

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Zicheng Lyu, Zengfeng Huang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Balancing Act: Learning with a Tiny Brain and a Slow Voice

Imagine you are a detective trying to solve a massive mystery, but you have two very strict rules. First, you can only carry a tiny notebook with you; if you write down too much, you have to throw something out to make room for new clues. Second, you can't shout your theories out loud immediately. Instead, you have to write a plan, go out and gather evidence based on that plan, come back, and then you are allowed to rewrite your plan for the next round. You can't change your mind while you are out in the field.

This is the world of "bandit problems," a famous puzzle in the science of decision-making. In this field, an agent (like a robot or a computer program) has to choose between different options to find the best one, like a gambler picking the best slot machine or a doctor picking the best medicine. The catch is that the agent doesn't know which option is best at the start; it has to learn by trying them out and seeing what happens. Usually, scientists assume the agent has a super-brain that remembers everything and can change its mind instantly after every single try. But in the real world, computers have limited memory, and sometimes we can't update our strategies instantly—we have to wait for a "batch" of results to come in.

This paper asks a fascinating question: If you are forced to use a tiny notebook (limited memory) and you can only update your plan a few times (limited batches), how badly will you mess up? Is it better to have a slightly bigger notebook and update your plan often, or a huge notebook and update rarely? The authors of this paper, Zicheng Lyu and Zengfeng Huang, dive deep into this trade-off to find the exact mathematical limit of how well you can learn under these constraints.

The Detective's Dilemma: Memory vs. Updates

The authors set up a game where a learner is trying to find the highest peak in a foggy, mountainous landscape. The landscape is smooth (mathematically, it's "Lipschitz"), meaning if you are close to a high point, you are probably near a high point. The learner can take steps (pulls) to measure the height, but they have two strict limits:

Memory Width ( $W$ ): After every step, the learner can only keep a tiny amount of information (a few bits) in their "live" notebook. They can't store the whole history of the trip.
Batch Depth ( $B$ ): The learner must group their steps into "batches." They pick a plan, take a bunch of steps, and only after all those steps are done can they look at the results and change their plan for the next batch. They can't change the plan while they are in the middle of the batch.

The big question is: How do these two limits work together? Can a super-wide memory make up for having very few chances to update? Or does having many updates make up for a tiny memory?

The Big Discovery: You Cannot Bypass the System

The paper's main finding is a bit of a bummer for anyone hoping to find a magic shortcut: Memory and updates are not interchangeable. You cannot just swap one for the other.

The authors prove that to do a good job, you need both enough memory to hold the important clues and enough updates to act on them. They found a new mathematical formula that describes the "regret" (how much worse you do compared to a perfect expert). This formula has three parts:

The difficulty of the landscape itself (how many mountains there are).
The penalty for not being able to update your plan often enough.
The new penalty: A specific cost that comes from trying to squeeze too much information through a narrow memory pipe with too few update opportunities.

Think of it like trying to send a long letter through a post office that only accepts small envelopes, and you can only mail a letter once a week.

If you have a huge memory (a giant warehouse of notes) but can only mail a letter once (one batch), you are stuck. You can't send the crucial details of the new clues you found because you can't change your plan until the week is over.
If you can mail a letter every day (many batches) but your envelope is tiny (low memory), you have to throw away most of your notes after every step. You might remember to go north, but you forget why you went north, so you can't refine your path.

The authors show that the worst-case performance is determined by the weakest link in this chain. If your memory is too small to hold the "map" of where the good spots are, having a million updates won't help. If you can't update your plan often enough, having a library of memory won't help either.

The "Information Routing" Bottleneck

The paper introduces a cool concept called Information Routing. Imagine the landscape is divided into many small regions. To find the best spot, the learner has to make a decision for each region: "Is this region worth exploring further?"

The problem is that the learner has to carry these decisions across the "batch boundaries" (the times when they are allowed to update).

The Memory ( $W$ ) limits how many decisions they can carry in their pocket at one time.
The Batches ( $B$ ) limit how many times they can stop, look at their pocket, and decide to change their route.

The authors prove that if you try to compress all your decisions into a tiny summary to save space, you lose too much detail. If you try to keep every detail, you run out of space. The optimal strategy is a delicate dance: keep just enough information to know which regions are "safe" to explore, and throw away the rest of the raw data immediately.

They found that to get close to the performance of a perfect, unlimited learner, you need a specific amount of memory (roughly the logarithm of the total time) and a specific number of updates (roughly the logarithm of the logarithm of the total time). If you have less than that, your performance drops significantly.

What This Means for the Future

The paper doesn't just say "it's hard." It gives a precise recipe for how hard it is. They proved that if you have enough memory (about $\log(T)$ bits, where $T$ is the total number of steps) and enough batches, you can almost match the performance of a learner with infinite memory and instant updates. But if you fall short on either, you hit a wall.

They also showed that being "smart" about when you update (using adaptive boundaries) doesn't actually help you beat the worst-case scenario. Whether you update at fixed times or try to be clever about it, the fundamental limits of your memory and update count still apply.

In short, this paper tells us that in the world of learning with limited resources, you can't have your cake and eat it too. You need a balance. You need a notebook big enough to hold the map, and you need enough chances to redraw that map. If you try to cut corners on either, the math says you will pay the price. It's a fundamental rule of the universe of learning: State width and update depth are partners, not substitutes.

Technical Summary: Information Routing across Batch Boundaries in Lipschitz Bandits

Problem Formulation
This paper investigates the fundamental tradeoff between state width (memory) and update depth (batch adaptivity) in stochastic Lipschitz bandits. The setting involves a learner interacting with an unknown mean reward function $f: [0, 1]^d \to [0, 1]$ that is 1-Lipschitz in the sup-norm. The learner operates under two simultaneous constraints:

Memory ( $W$ ): After every pull, the learner retains at most $W$ bits of mutable, reward-dependent state.
Batches ( $B$ ): The learner's actions are divided into at most $B$ committed batches. At a batch boundary, the current state commits the next boundary and the entire sequence of actions for that batch. Rewards observed within a batch update the state online but cannot alter the already committed action tape.

The objective is to characterize the minimax expected pseudo-regret, $R_T(B, W)$ , as a function of the horizon $T$ , dimension $d$ , memory budget $W$ , and batch budget $B$ .

Methodology and Technical Approach
The authors establish a minimax frontier by constructing a "hard family" of problem instances that exposes two distinct resource bottlenecks simultaneously:

Verification Budget: The total number of samples available in the horizon limits how many local improvements can be verified.
Routing Budget: The boundary states (the state at the end of each batch) limit how many regional decisions regarding where to send future experiments can be preserved and communicated to subsequent batches.

Lower Bound Construction:
The lower bound relies on a geometric construction involving $m \asymp s^{-d}$ separated pairs of regions at scale $s$ . Within each region, there are $q \asymp (s/r)^d$ probes at a finer scale $r$ . A latent routing vector $V \in \{0, 1\}^m$ selects the "good" side of each pair.

Information Routing Constraint: To achieve low regret, the learner must identify the correct side of each pair. This requires the committed action transcript to encode $\Theta(s^{-d})$ bits of information about $V$ .
Entropy Bottleneck: The total entropy of the boundary states across $B$ batches is bounded by $(B-1)W$ . Using a stopped change-of-measure argument and Fano's inequality, the authors show that if the boundary-state entropy budget is insufficient to encode the routing decisions, the learner incurs high regret by misrouting verification efforts to unselected regions.
Update Depth Obstruction: A separate adaptive-grid construction (adapted from Feng et al., 2024) provides a lower bound dependent solely on $B$ , independent of $W$ , showing that even with infinite memory, limited batches restrict the rate of refinement.

Upper Bound Construction:
The matching upper bound employs a policy that maintains a safe active-set mask (a binary vector indicating which regions contain potential maximizers) while streaming and erasing fine-grained verification statistics.

Static Boundaries: The policy uses static batch boundaries.
Serialization vs. Hierarchy:
- When the active-set mask fits in memory ( $W$ is large), the learner uses an in-memory hierarchical refinement to update all coordinates simultaneously.
- When the mask exceeds memory, the learner uses a serialized construction. It regenerates memory-sized fragments of the mask, uses them to commit corresponding child probes, updates a global best-child record, and erases the fragment. This allows the learner to process the active set in fragments without exceeding the $W$ -bit limit.
Key Mechanism: Verification statistics are accumulated online, compared against a resident best-arm record, and immediately erased. Only the active-set mask (or its fragments) and logarithmic control records persist across boundaries.

Key Results
The paper characterizes the minimax regret up to logarithmic factors. The regret is governed by the worst of three barriers:

Sequential Estimation: $T^{(d+1)/(d+2)}$ (the standard Lipschitz bandit rate).
Batch Depth: A term dependent on $B$ derived from adaptive-grid limitations.
Width–Depth Interaction: A new term capturing the joint constraint:
$T^{\frac{d+2}{d+3}} \left(1 + (B-1)W\right)^{-\frac{1}{d(d+3)}}$

Formal Frontier (Theorem 3.4):
For $W \gtrsim_d \log(eT)$ , the minimax regret satisfies:
$R_T(B, W) \asymp \max \left( T^{\frac{d+1}{d+2}}, \frac{T^{\beta_{d,B}}}{B^2}, T^{\frac{d+2}{d+3}} (1 + (B-1)W)^{-\frac{1}{d(d+3)}} \right)$
where $\beta_{d,B} = \frac{d+1}{d+2} \frac{1}{1 - (d+2)^{-B}}$ .

Special Cases and Implications:

Unrestricted Memory ( $W \to \infty$ ): The result recovers the full-dimensional worst-case batch-only frontier established by Feng et al. (2024).
Fully Sequential ( $B=T$ ): The result recovers the sequential minimax regret with logarithmic memory ( $W \asymp \log T$ ), consistent with Zhu and Huang (2025).
Non-Interchangeability: The product $(B-1)W$ appears in the exponent, proving that state width and update depth are complements, not substitutes. A single wide state cannot generally replace a sequence of narrower states recomputed between rounds of exploration.
Batch Complexity: To achieve near-sequential regret, the number of batches $B$ must scale as $\log \log T$ (if $W$ is sufficient), and the boundary-state entropy $(B-1)W$ must scale as $T^{d/(d+2)}$ .

Significance and Claims
The paper claims to resolve the structural question of how memory and adaptivity jointly determine performance in nonparametric optimization.

Information Routing: The authors introduce the concept of "information routing," where the causal transport of reward-dependent decisions across batch boundaries is the limiting factor. The boundary states act as a bottleneck for the entropy of these decisions.
Optimality: The matching upper and lower bounds (up to logarithmic factors) demonstrate that static batch boundaries are sufficient to achieve the minimax rate; predictable adaptive boundaries do not improve the worst-case order.
Unified View: The framework unifies the batch-only and finite-memory sequential models, showing that the "frontier" is a single surface governed by three primitive resources: samples for verification, state for regional routing, and depth for adaptive refinement.

The authors note that removing the logarithmic losses, characterizing the sub-logarithmic memory regime, and obtaining instance-dependent analogues remain open problems.