arXiv:2608.18061cs.LGcs.GT2026-08

用博弈论统一解释贝叶斯更新与后悔的数学机制。

The concentration game: Bayesian updating, regret, and information

  • 构建双人零和博弈,让贝叶斯更新与后悔值自然涌现。
  • 后悔分解为信息损失、重校准漂移与比较器相对先验的信息量。
  • 适用于多臂赌博机、后验采样等场景,提供统一分析视角。

我们构建了一个两玩家零和重复博弈,其中学习者与自然对抗,其价值函数同时生成贝叶斯更新和指数权重后悔的精确表达,并揭示了广泛集中现象共有的比较类变分形式。终端收益是任意比较器在固定相对熵下从先验中能获得的最大收益,单步约束是对自然在学习者混合策略下的信息预算限制。在学习者其他动作不受限的情况下,吉布斯/贝叶斯权重成为唯一的贝尔曼均衡策略——使每轮损失不依赖于自然移动方向的混合策略,对数归一化项则充当价值函数。后悔值精确分解为三部分:反映观测结果变化的每轮信息损失、准确体现跨轮次度量尺度变化的加性重校准漂移,以及比较器相对于先验携带的信息量。方差与有界范围的代理方法只是该分解的宽松松弛,该分解具有普遍性并统御所有标准后悔界。双方策略可逐项由分解读出,重复博弈产生信息论意义上的自对弈账本,替代传统的二次变差近似。相同的比较类几何也解释经典大偏差界,而多臂赌博机、后验采样、聚合与提升等方法均为此后悔分解的特例。

原文摘要 · Abstract (English)

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.

贝叶斯推理后悔分析信息论博弈论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。