The concentration game: Bayesian updating, regret, and information

Overview§

The paper introduces a two-player zero-sum repeated game between a learner and nature. The game's value identity simultaneously generates Bayesian updating and an exact accounting of exponential-weights regret. The terminal payoff is the maximum gain a comparator can achieve at a fixed relative entropy from the prior, while the one-step constraint is an information budget on nature's move under the learner's mixed action.

Core Mathematical Formulation§

Let the learner choose mixed actions $p_t$ over a set of experts, and nature chooses outcomes $y_t$. The per-round loss is $\ell(p_t, y_t)$. The game value satisfies a Bellman recursion:

$$V_t(\pi) = \min_{p} \max_{y: D_{\text{KL}}(y \| p) \le \eta} \left[ \ell(p, y) + V_{t+1}(\pi') \right]$$

where $\pi$ is the current belief (posterior), and $\pi'$ is updated via Bayes rule. The key result is that Gibbs/Bayes weights emerge as the unique Bellman equalizer: the mixed action $p_t$ makes the per-round loss independent of nature's direction, with log-partition functions serving as value functions.

Exact Regret Decomposition§

For any comparator $f$, the regret decomposes exactly into three parts:

1. Per-round information loss: reflecting variation in observed outcomes.
2. Retempering drift: accounts for changes in measurement scale between rounds.
3. Comparator information: relative entropy of the comparator to the prior.

Mathematically:

$$\text{Regret}_T(f) = \sum_{t=1}^T I_t + \Delta_T + D_{\text{KL}}(f \| \pi_0)$$

This identity is exact and general. Variance and bounded-range proxies that drive standard regret bounds are shown to be looser relaxations of this decomposition.

Game Strategies§

Both players' optimal strategies are read off term-by-term from the decomposition. The learner updates a posterior via Bayes rule (with log-partition as value), while nature chooses outcomes that maximize the information loss subject to an entropy budget. Repeated play yields an information-theoretic ledger of self-play, replacing the usual quadratic-variation surrogate.

Connections and Specializations§

The same comparator-class geometry accounts for classical large-deviation bounds. Methods across bandits, posterior sampling, aggregation, and boosting are shown to be specializations of the single regret decomposition.

Illustrative Python/PyTorch Sketch§

import torch
import torch.nn.functional as F

def bayes_update(log_prior, log_likelihood):
    """Performs Bayesian update using log-partition as value."""
    log_posterior = log_prior + log_likelihood
    log_partition = torch.logsumexp(log_posterior, dim=-1)
    posterior = torch.exp(log_posterior - log_partition.unsqueeze(-1))
    return posterior, log_partition

def exponential_weights_regret_step(losses, prior, learning_rate=1.0):
    """One step of exponential weights with entropy budget."""
    # losses: [num_experts]
    # prior: [num_experts]
    log_prior = torch.log(prior)
    # Nature's move: choose outcome that maximizes information loss
    # Learner's mixed action is Gibbs weights
    log_posterior = log_prior - learning_rate * losses
    posterior, log_partition = bayes_update(log_prior, -losses)
    # Regret decomposition terms
    info_loss = losses @ posterior - log_partition
    drift = learning_rate * losses.var()  # simplified retempering drift
    return posterior, info_loss, drift

Significance§

This work provides a unifying theoretical framework that ties Bayesian inference, online learning, and concentration inequalities into a single game-theoretic structure. It offers practitioners an exact decomposition of regret, which can guide algorithm design and sharpen existing bounds.