Balsubramani paper shows exact regret decomposition for Bayesian updates

Akshay Balsubramani's paper 'Adaptive Bayes exactly tracks information over intrinsic time' introduces a fundamental identity for sequential decision-making algorithms. The identity shows that on each round, the learner's excess loss relative to any comparator equals the sum of an immediate payment for the uncertainty exposed by that round and a reduction in the information distance from the current weights to the comparator. This decomposition is exact, not an inequality, meaning that all slack in traditional worst-case bounds vanishes. The cumulative payments define a pathwise measure called 'intrinsic time', which tracks the total uncertainty realized by the data sequence.

The framework covers a wide range of algorithms, including Hedge (multiplicative weights), optimistic and side-information variants, continuous priors, boosting, online convex optimization, contextual bandits, and repeated games. Because the identity is exact, favorable stochastic or low-noise regimes automatically lead to tighter regret guarantees without additional analysis. This provides a unifying theoretical lens for understanding when and why adaptive learning algorithms work, and could simplify the design of new online learning methods.