In sequential decision-making and uncertainty quantification, there is an intuitive temptation to scale resources linearly with the complexity of a task. If an agent operates over a time horizon $T$, it seems natural that it should continuously explore, or that an ensemble approximating a complex posterior distribution should grow significantly to maintain accuracy.
However, a powerful convergence of recent research demonstrates that logarithmic scaling is fundamentally sufficient. Whether measuring the number of models needed in an ensemble, the frequency of exploration steps, or the samples required to withstand heavy-tailed noise, a logarithmic relationship relative to the horizon or model space provides an optimal statistical guarantee. This insight bridges the gap between computationally lightweight heuristics and rigorous regret bounds.
The Pitfalls of Persistent Exploration
Traditional multi-armed bandit and linear bandit algorithms (such as standard Upper Confidence Bound variants) are designed to minimize cumulative regret by exploring indefinitely. They maintain a steady rate of exploration to ensure they never miss the optimal action. However, this persistent experimentation can be highly counterproductive.
As Ozbay et al. demonstrate, when the objective shifts from maximizing the sum of rewards to maximizing the peak performance of a single trained arm, indefinite exploration causes linear regret. To maximize the ultimate performance of a single selection, an algorithm must know when to stop searching and fully commit its remaining budget to the identified leader.
Even in standard cumulative reward settings, constant exploration is often unnecessary. Zhang et al. show that traditional regret-minimizing algorithms over-explore by sampling sub-optimal options for a duration proportional to the entire time horizon. They prove that exploration can be safely restricted to a logarithmic scale relative to the time horizon without sacrificing optimal cumulative rewards.
Building on this insight, Lee et al. introduce a framework showing that optimal asymptotic regret bounds can be maintained even when exploration occurs infrequently, provided the total number of exploration steps crosses a logarithmic threshold relative to $T$. By reducing the frequency of exploration and interleaving it with greedy actions, systems avoid the finite-time regret penalties of excessive experimentation.
Linear Exploration: [Explore][Explore][Explore][Explore][Explore] -> High Regret
Logarithmic Threshold: [Explore]...[Greedy]......[Explore]......... -> Optimal Regret
Why Small Ensembles Suffice
The principle of logarithmic sufficiency is highly visible in Ensemble Sampling, a practical alternative to Thompson Sampling. Thompson Sampling requires sampling from an exact posterior distribution, which is computationally intractable for complex models like deep neural networks. To circumvent this, Lu et al. proposed maintaining a small collection of statistically plausible models to approximate the posterior.
For years, a gap remained between the empirical success of ensemble sampling and its theoretical foundations, with early theories suggesting that massive ensembles were required to guarantee convergence. Recent breakthroughs have closed this gap by proving that the number of models in an ensemble only needs to scale logarithmically with the time horizon $T$.
Janz et al. and Lee et al. independently proved that an ensemble size proportional to the logarithm of the time horizon is sufficient for near-optimal exploration in linear bandits. As Lee et al. explain, a logarithmic number of models ensures that at least one model in the set remains optimistic enough to drive necessary exploration, while keeping the computational overhead significantly lower than linear-growth alternatives.
When moving to high-dimensional settings, Li et al. and Li et al. demonstrate that this efficiency holds true even for complex architectures. They show that an ensemble size scaling linearly with the problem's dimensionality and logarithmically with time is sufficient to match exact Thompson Sampling, completely bypassing the need to scale with the number of available actions.
Logarithmic Efficiency in Estimation and Selection
This logarithmic phenomenon extends beyond exploration schedules into the realms of robust estimation, model selection, and classical supervised learning.
Consider the challenge of model selection when an agent faces a massive number of candidate feature maps or parameter clusters. Traditional methods suffer from a regret penalty that scales heavily with the number of models $M$. However, Moradipari et al. show that by reducing the bandit problem to a full-information regression task, the regret bound scales with $\sqrt{\log M}$ instead of $\sqrt{M}$. This logarithmic scaling allows systems to evaluate exponentially larger sets of potential models without a proportional increase in learning time.
In the presence of extreme, "super heavy-tailed" noise (where variance or even the mean may not exist), Zhong et al. utilize a Mean of Medians estimator. The number of samples required for this estimator to concentrate effectively scales logarithmically with the total time horizon, allowing algorithms to treat wild noise as if it were well-behaved sub-Gaussian noise without compromising sub-linear regret.
Finally, this principle validates long-standing heuristics in supervised learning. Larsen proved that bootstrap aggregation (bagging) is an optimal PAC learner in the realizable setting, requiring only a logarithmic number of bootstrap samples relative to the size of the training set to achieve optimal sample complexity.
Intuition: Why Does Logarithmic Scaling Work?
To understand why a logarithmic relationship is the natural threshold across these diverse problems, consider how information accumulates in stochastic environments.
When an agent or an ensemble interacts with an environment, the initial data points provide massive reductions in uncertainty. The marginal value of additional data points drops off exponentially. A logarithmic exploration schedule or ensemble size perfectly mirrors this information curve through two primary mechanisms:
Optimism Maintenance
In ensemble sampling, you do not need an infinite number of particles to map the entire posterior distribution. You only need enough particles to ensure that the maximum of your samples occasionally samples the upper tail of the true distribution to maintain an optimistic drive. Because the maximum of $N$ sub-Gaussian variables grows proportionally to $\sqrt{\log N}$, a logarithmic number of particles is precisely what is required to match the exploration drive of a continuous Gaussian posterior.
Error Concentration
For robust estimators (like Mean of Medians) or PAC learners (like bagging), the probability of an individual sample or bootstrap batch failing to represent the true distribution decays exponentially. By taking a logarithmic number of samples or batches, the failure probability can be bounded by a term inversely proportional to the time horizon $T$ or dataset size, ensuring global convergence with minimal overhead.
Key Foundational Work
Ensemble Sampling (2017) — contributed 2 concept elements to this direction.
Training a Single Bandit Arm (2021) — contributed 2 concept elements to this direction.
Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs (2021) — contributed 1 concept elements to this direction.