In classical online learning, we assume a "fully sequential" world: an agent takes an action, observes a reward, and immediately updates its strategy before the next step. While mathematically elegant, this is often a fantasy in production. In clinical trials, doctors cannot change protocols for every patient; in online advertising, servers cannot synchronize global models every millisecond; and in complex simulations, we often run experiments in parallel batches.
The central discovery across this research is that adaptivity is surprisingly cheap. You do not need to update your policy after every observation to achieve near-optimal performance. In fact, updating a model only a handful of times—often following a double-logarithmic schedule—is sufficient to match the performance of an agent that learns in real-time.
The Adaptivity Gap
The core challenge in batched learning is the "exploration-exploitation" lag. If you pull an arm 1,000 times in a single batch, you cannot use the results of the 1st pull to inform the 100th. This creates a potential for "regret"—the lost opportunity cost of not playing the best arm.
Early work by Vianney Perchet, Sylvain Chassang, and Erik Snowberg in Batched Bandit Problems established a fundamental principle: the number of batches required to achieve minimax-optimal regret scales only double-logarithmically ($O(\log \log T)$) with the time horizon $T$.
To put this in perspective: if you have a horizon of one billion trials, a fully sequential algorithm updates one billion times. A batched algorithm might only need to update five or six times to achieve nearly the same total reward.
The Mechanism of Exponential Growth
Why does such a small number of updates work? The intuition lies in how we schedule the batches. Most batched algorithms, such as the BaSE algorithm by Zijun Gao and Yanjun Han in Batched Multi-armed Bandits Problem, use an exponentially increasing batch size.
- Early Stages: Batches are small. We update frequently when our uncertainty is high, quickly narrowing down the set of "good" actions.
- Later Stages: Batches grow massive. Once we have a high-confidence estimate of the best action, the risk of "missing" a slightly better update is outweighed by the efficiency of staying the course.
For instance, Nikolai Karpov and Qin Zhang demonstrated in Batched Thompson Sampling for Multi-Armed Bandits that by scaling batch sizes at a double-exponential rate, one can maintain instance-independent regret bounds with only $O(\log \log T)$ batches.
Scaling to Complex Models
This "rare update" property isn't limited to simple multi-armed bandits; it extends to high-dimensional and non-linear settings.
- Linear Contextual Bandits: Zihan Zhang and Yuan Zhou proved in Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits that even with complex features, $O(\log \log T)$ updates are sufficient. Sanghoon Yu and Min-hwan Oh further refined this in Optimal and Practical Batched Linear Bandit Algorithm, showing these bounds hold across both small and large action spaces.
- Neural Bandits: For deep learning models, where retraining after every step is computationally prohibitive, Quanquan Gu and Dongruo Zhou showed in Batched Neural Bandits that batching provides a massive boost to speed without sacrificing the convergence properties of the neural agent.
- Reinforcement Learning: The principle even reaches multi-agent settings. Dan Qiao and Yu-Xiang Wang established in Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints that zero-sum games can be solved with only $O(\log \log K)$ policy updates.
Reducing Online Learning to Offline Oracles
A major practical benefit of the batched approach is the ability to use offline oracles. In a fully sequential setting, you need an algorithm that can update incrementally (online). In a batched setting, you can treat each update as a standard supervised learning problem.
The FALCON algorithm, introduced by David Simchi-Levi and Yunzong Xu in Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability, exemplifies this. By reducing contextual bandits to standard offline regression and calling that regression oracle only a logarithmic number of times, they bridged the gap between theoretical optimality and practical engineering. This allows practitioners to use state-of-the-art, "black-box" regression tools (like XGBoost or deep networks) within a bandit framework without needing specialized online versions of those tools.
The Fundamental Limit
While $O(\log \log T)$ is often enough for minimax (worst-case) regret, Tianyuan Jin and Quanquan Gu proved in Almost Optimal Anytime Algorithm for Batched Multi-Armed Bandits that this is a hard theoretical floor. No "anytime" algorithm (one that doesn't know the end time $T$ in advance) can be regret-optimal with fewer than $\Omega(\log \log T)$ batches.
This research direction suggests a shift in how we view adaptive systems: rather than striving for "real-time" updates, the most efficient systems are those that strategically wait, accumulating enough data to make each rare update count.