Abstract
While the benefits of interactivity in decision-making are well-documented, the temporal evolution of information gain during the "burn-in" period remains poorly understood. This paper investigates the classic multi-armed bandit (MAB) problem to characterize how optimal success probability ($p^*_t$) and mutual information ($I^*_t$) evolve over time. We identify a distinct quadratic growth phase in mutual information and demonstrate a decoupling between information maximization and optimal learning.
Introduction
In interactive decision-making, such as the multi-armed bandit problem with $n$ arms, algorithms can achieve a $\Theta(\log n)$ gain in sample complexity compared to non-interactive strategies. However, most research focuses on asymptotic performance or final regret. This study shifts focus to the "burn-in" period—the regime where the time $t$ is smaller than the full sample complexity—to understand how an algorithm accumulates information and when "aha moments" occur.
The Phases of Information Evolution
The paper identifies four distinct regimes for the evolution of mutual information ($I^*_t$):
- Initial Linear Phase ($t\Delta^2 \le 1$): Information grows at a rate of $\Theta(t\Delta^2/n)$, similar to non-interactive sampling.
- Quadratic Growth Phase ($1 < t\Delta^2 \le \log n$): A striking acceleration where information grows as $\Theta((t\Delta^2)^2/n)$. This "boost" occurs because interaction allows the learner to focus on better arms, creating a feedback loop.
- Second Linear Phase ($\log n < t\Delta^2 \le n$): Information gain stabilizes with a $\log n$ advantage over non-interactive methods.
- Saturation ($t\Delta^2 > n$): The learner identifies the best arm with high confidence, and information reaches its maximum of $\log n$ bits.
Crucially, the authors find a decoupling of learning and information. While Fano's Inequality typically links these two, this work proves that an algorithm can achieve optimal success probability without necessarily maximizing mutual information, suggesting that "maximalist" information gain is not a prerequisite for optimal learning.
Technical Framework
The authors establish these results through a combination of algorithmic construction and information-theoretic lower bounds. They propose a Sequential Probability Ratio Test (SPRT) based algorithm that uses biased random walks to prune suboptimal arms efficiently.
The proof strategy involves a "Change-of-Divergence" technique for mutual information upper bounds and a "Boosting Argument" to relate performance in early stages to established end-game limits. As shown in the roadmap above, the analysis is bifurcated into achievability and converse results for both success probability and mutual information across large and small time regimes.
Conclusion and Future Work
This case study provides a precise temporal map of information gain in MABs. While the results are derived for a stylized Bernoulli model, they offer foundational insights for the broader Decision-Estimation Coefficient (DEC) framework. Future research will explore whether these growth phases persist in more complex structured bandit problems or when using random stopping times instead of fixed budgets.
Summary updated