In traditional sequential decision-making frameworks—such as multi-armed bandits, online optimization, and reinforcement learning (RL)—an agent is typically assumed to operate in a tight, continuous feedback loop. After every single action, the agent observes a reward or state transition, immediately updates its internal model, and deploys a revised policy for the very next step.
While mathematically convenient, this round-by-round adaptation is often impractical. In real-world systems, updating a policy continuously introduces severe bottlenecks:
- Computational Overhead: Re-solving complex linear programs in serverless function placement (Richard Combes et al.) or combinatorial matching problems (Min-hwan Oh et al.) at every time step is computationally intractable.
- Deployment and Communication Costs: In clinical trials, large-scale advertising, or distributed systems, redeploying a new policy or synchronizing parameters across nodes incurs a heavy "communication tax" (Hossein Esfandiari et al.).
This raises a fundamental question: How frequently must an agent update its policy to maintain optimal performance?
A robust body of research demonstrates that continuous adaptation is unnecessary. By scheduling updates on a logarithmic or double-logarithmic scale relative to the time horizon, algorithms can drastically reduce the frequency of policy switches while matching the theoretical performance guarantees (regret bounds) of fully sequential methods.
The Core Intuition: Diminishing Returns of Information
To understand why logarithmic scheduling works, we must look at how an agent's uncertainty shrinks over time.
In stochastic environments, the statistical confidence interval around an action's true value typically scales as $O(1/\sqrt{N})$, where $N$ is the number of samples observed for that action.
Imagine an agent has already collected $N = 10$ samples. Collecting 10 more samples doubles its data, significantly shrinking its uncertainty and altering its optimal strategy. However, if the agent has already collected $N = 10,000$ samples, collecting 10 more provides a negligible change to its confidence interval. To achieve a comparable structural reduction in uncertainty, the agent would need to collect another 10,000 samples.
Because information gain exhibits rapidly diminishing returns, updating a policy between these exponential milestones yields negligible performance gains. This insight, formalized by Vianney Perchet et al., implies that we can group observations into discrete batches or epochs that grow exponentially in size.
The Mathematical Limits of Batching
The frequency of required updates depends heavily on the learning objective. The literature establishes two primary regimes based on the type of regret being minimized:
1. Minimax Regret: $O(\log \log T)$ Batches
If the goal is to minimize worst-case (minimax) regret over a time horizon $T$, the frequency of feedback can be reduced to a double-logarithmic scale. Zijun Gao et al. and Vianney Perchet et al. proved that a mere $O(\log \log T)$ batches are sufficient to achieve the same minimax regret rate as fully sequential algorithms.
When the total time horizon $T$ is unknown in advance (the "anytime" setting), Jing Tang et al. proved a fundamental lower bound: no anytime algorithm can remain regret-optimal using fewer than $\Omega(\log \log T)$ batches. This defines the absolute minimum communication frequency required for an agent to remain optimal without knowing when its task will end.
2. Problem-Dependent Regret: $O(\log T)$ Batches
If the goal is to achieve optimal problem-dependent regret—which exploits the specific performance gaps between optimal and sub-optimal actions—the learner requires more frequent updates. Zijun Gao et al. showed that this regime requires a number of interaction rounds that scales logarithmically ($O(\log T)$) with the total time horizon. Arpit Agarwal demonstrated a similar result in the context of dueling bandits, showing that logarithmic batching preserves asymptotic regret optimality while insulating large-scale recommendation systems from real-time retraining overhead.
Triggering Mechanisms: How to Schedule Updates
Practitioners implement logarithmic update scheduling using two primary mechanisms: time-based doubling windows and data-driven local triggers.
Time-Based Doubling Windows
The simplest approach divides the time horizon into episodes that grow exponentially in length (e.g., updating at $t = 2, 4, 8, 16, \dots$).
Fully Sequential: |x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x| (16 updates)
Exponential Epochs: |x|x |x |x |x | (5 updates)
Min-hwan Oh leveraged this strategy in multinomial logit contextual bandits. By keeping the policy static within an exponentially lengthening episode, the samples collected during that period remain statistically independent. This allows the algorithm to apply tighter confidence bounds without requiring purely random exploration. Similarly, Uri Sherman et al. applied a doubling-window update strategy to online convex optimization, proving that "laziness" minimizes switching costs while maintaining competitive regret bounds.
Local Information-Gain Triggers
In high-dimensional problems or reinforcement learning, a global time trigger is often too coarse. An agent might visit one state thousands of times while barely exploring another. In these scenarios, updates are triggered locally when the data accumulated for a specific state, action, or context doubles.
For instance, Yu Bai et al. introduced a logarithmic triggering sequence for Q-learning, where a state-action pair's policy is only refreshed when its individual visit count reaches specific exponential milestones (e.g., $1, 2, 4, 8, \dots$). This ensures that the frequency of policy changes decreases over time while maintaining sufficient adaptivity for convergence. Jiafan He et al. utilized a similar visit-count doubling strategy to restrict expensive value iteration steps to a logarithmic scale relative to the total number of interactions.
Scaling to Complex Environments
The principle of logarithmic scheduling is not limited to simple multi-armed bandits; it scales effectively to complex, high-dimensional settings.
Contextual Linear Bandits
In contextual settings, the action space or context changes at every step, making continuous updates particularly expensive. Osama A. Hanna et al. and Osama A. Hanna et al. demonstrated that stochastic contextual linear bandits can achieve near-optimal regret with only $O(\log \log T)$ policy updates. By replacing aggressive action elimination with a "soft elimination" strategy that shapes the action set across batches, they proved that practitioners can significantly reduce model retraining frequency in applications like clinical trials without sacrificing long-term performance.
Continuous-Time Reinforcement Learning
In continuous control environments, where observations arrive in a continuous stream, updating after every measurement is impossible. Runze Zhao et al. designed the PURE framework, which triggers policy updates only when the cumulative model error exceeds a predefined threshold. This error-driven approach naturally yields a logarithmic reduction in update frequency, cutting computational training time by up to 50% while maintaining optimal policy performance.
General Function Approximation
To unify these empirical successes, Nuoya Xiong et al. introduced a framework utilizing the Eluder Condition. They proved that for a wide class of sequential decision-making models—ranging from tabular MDPs to complex partially observable MDPs (POMDPs)—agents can achieve near-optimal regret while restricting policy switches to a logarithmic function of the total episodes. This confirms that sample efficiency and low update frequency can coexist across virtually all standard reinforcement learning architectures.
Key Foundational Work
Near-optimal Regret Bounds for Reinforcement Learning (2008) — contributed 2 concept elements to this direction.