Search papers, labs, and topics across Lattice.
This paper explores a two-player zero-sum repeated game framework where a learner interacts with nature, integrating Bayesian updating with a novel regret decomposition that captures various concentration phenomena. The authors derive a unique Gibbs/Bayes weight strategy that ensures the learner's per-round loss remains invariant to nature's movements, while also providing an exact accounting of regret through three distinct components. The findings reveal that traditional regret bounds can be viewed as looser relaxations of this comprehensive decomposition, offering a unified perspective on various machine learning methodologies such as bandits and boosting.
Regret in zero-sum games can be precisely decomposed into information loss, measurement drift, and prior knowledge, reshaping our understanding of learning dynamics.
We give a two-player zero-sum repeated game between a learner and nature whose value identity generates Bayesian updating and an exact accounting of exponential-weights regret at once, and supplies the comparator-class variational form that a wide class of concentration phenomena share. The terminal payoff is the most a comparator can gain at fixed relative entropy from the prior, and the one-step constraint is an information budget on nature's move under the learner's mixed action. With the learner's move otherwise unrestricted, Gibbs/Bayes weights emerge as its unique Bellman equalizer -- the mixed action that makes the per-round loss independent of which direction nature moves -- with log-partition functions playing the role of value functions. The regret decomposes exactly into three parts: a per-round information loss reflecting the variation in observed outcomes, an additive retempering drift that accounts exactly for any change of measurement scale between rounds, and the information the comparator carries relative to the prior. The variance and bounded-range proxies that drive standard regret bounds are looser relaxations of this decomposition, which holds generally and governs them all. Both players' strategies are read off from the decomposition term by term, and repeated play yields an information-theoretic ledger of self-play in place of the usual quadratic-variation surrogate. The same comparator-class geometry accounts for the classical large-deviation bounds, and methods across bandits, posterior sampling, aggregation, and boosting are specializations of the one regret decomposition.
