Adaptive Bayes exactly tracks information over intrinsic time
Akshay Balsubramani
Abstract
Bayesian and multiplicative-weights updates reweight experts, models, or actions from sequential feedback. We show that the regret of any such update obeys an exact information-accounting identity. On each round, the learner's excess loss to any chosen comparator is the sum of an immediate cost for the uncertainty exposed by the round and a reduction in the information distance from the learner's current weights to the comparator. The cumulative cost defines a pathwise uncertainty clock, the intrinsic time of the realized sequence. Summing one-step balances yields two exact adaptive decompositions of cumulative regret, one for each natural way of composing the update across rounds. Because the decompositions are exact, favorable stochastic or low-noise regimes appear as self-bounding properties of the realized intrinsic time. The accounting also fixes a learning rate, inverse in the square root of intrinsic time. That schedule is competitive with adaptive baselines in selected online-learning settings. The same calculus covers Hedge, optimistic and side-information variants, continuous priors, boosting, online convex optimization, contextual bandits, and repeated games: the pathwise account is the same in every case.
Topics
Classified with taxonomy v2 on Sat, 5 Sept 2026.