乘法权重更新方法

权重不是在猜“谁永远正确”，而是在记录每个动作至今仍值得保留多少相对可信度。指数更新把累计损失变成乘法衰减，归一化后，高损失动作自然失去概率质量，却不会因一次错误被永久删除。

总权重势函数同时面向两端：上界记录算法每轮平均损失让整体质量缩小多少，下界保留任意固定比较动作剩下的质量。两端夹住同一个 $W_{T+1}$，便把算法损失与最佳固定动作连接起来。

线性化版本与范围 ​

有些文献采用 $w_{t+1,i}=w_{t,i}(1-\eta {\ell }_{t,i})$。为保持权重非负，需 $\eta {\ell }_{t,i}\le 1$，并用 $e^{-x}$ 与 $1-x$ 的比较重新推导常数。收益版会提升高收益动作而不是惩罚高损失动作。把这些式子拼接，会得到错误的学习率范围。

关系与边界 ​

Hedge理路指数权重与 HedgeHedge algorithm · exponential weights在全信息有界损失下按累计损失指数加权，并取得平方根级专家 regret。是全信息有界损失上的清晰实例；Weighted Majority理路Weighted Majority 算法Weighted Majority · 加权多数算法在二元在线预测中，对犯错专家乘法降权并按剩余权重多数表决。只在二元错误后乘固定因子。势能法理路势能法Potential method用数据结构状态势函数的增量调整单步记账，以控制操作序列的总成本。在这里跟踪总权重的指数增长，而算法分析中的摊还势能通常比较单次真实成本，目的不同。不是任何“把数乘到权重上”的启发式都继承上述定理。

从博弈收益表构造全信息反馈 ​

设玩家 $i$ 有 $K_i\ge 2$ 个动作，收益处于 $[m_i,M_i]$，记 $B_i=M_i-m_i>0$。观察到其他玩家本轮动作 $s_{-i}^t$ 后，若知道自己的收益表，就能为每个候选 $b$ 计算

将这一整条向量代入指数更新即可。观察自己取得的一个收益数值，通常不足以重建其他动作的反事实收益，因此这个协议要求完整反馈。常数收益玩家 $B_i=0$ 没有获利偏离，可直接忽略，不做除法。

例如粗相关均衡理路粗相关均衡Coarse correlated equilibrium · CCE对联合动作分布检验事先固定的单方偏离，并把经验分布的约束违反量精确写成平均外部遗憾。页的循环博弈中，收益范围是 $[-1,1]$，所以 $B_i=2$。行玩家看到对方选 $0$ 时，三个候选收益为 $(0,1,-1)$，对应损失 $(1/2,0,1)$。从权重 $(1,1,1)$ 出发，一次更新后得到 $(e^{-\eta /2},1,e^{-\eta })$。若下一轮对方选 $1$，候选损失是 $(1,1/2,0)$，第二次更新后权重为 $(e^{-3\eta /2},e^{-\eta /2},e^{-\eta })$。权重记录的是每个固定动作的累计损失，并不只更新实际选中的那个坐标。

分布反馈：平均各轮乘积 ​

先考虑没有动作抽样误差的协议。每轮玩家提交分布 $p_i^t$，反馈为对手当轮独立分布下每个动作的完整期望收益

用 $(M_i-g_i^t(b))/B_i$ 更新，玩家本轮收益按 $\sum _b{p}_i^t(b)g_i^t(b)$ 计算。将势函数界乘回 $B_i$，对每个固定动作 $b$ 有

输出

左边除以 $T$ 正好是该联合分布的固定偏离增益。因此 ${\bar{\mu }}_T$ 是确定性的 $\epsilon$-CCE，其中

这个输出可以理解为先均匀抽一轮，再按那一轮的分布独立抽各人的动作。共同的轮次会引入相关性；一般有 $T^{-1}\sum _t\prod _i{p}_i^t\ne \prod _i(T^{-1}\sum _t{p}_i^t)$。本协议还确实需要完整期望向量，不能把只看到对手一次抽样动作的反馈当成同一个对象。

实际动作反馈：加入抽样误差 ​

现在每轮各玩家根据历史 $H_{t-1}$ 选择分布，并在给定历史后独立抽取本轮动作。轮后观察对手动作、重建上面的完整损失向量，再更新。别人可以适应过去，但不能看见玩家 $i$ 的本轮抽样结果后才决定本轮动作；这正是在线协议理路在线学习协议Online learning protocol学习器按轮先行动、再接收结果与反馈的序贯决策协议。中的非预见条件。

对这些随机生成的实际损失向量，势函数界依然逐路径成立。它比较的基线却是本人混合收益 $\sum _b{p}_i^t(b)u_i(b,s_{-i}^t)$，还不是实际收益 $u_i(s^t)$。令两者之差为

在给定 $H_{t-1}$ 和对手本轮动作后，本人的动作仍服从 $p_i^t$，所以这个差的条件期望为零；再取一次条件期望得 $\mathbb{E}[Z_{it}\mid H_{t-1}]=0$。同时 $|Z_{it}|\le B_i$。把实际累计收益加减进势函数比较式，可得

因此 $\mathbb{E}{R}_i^{\mathrm{ext}}(T)\le B_i\sqrt{T\log K_i/2}$。这不能保证每次输出的经验分布都是同一误差的 CCE；随机波动在单次历史中仍然存在。不过每个固定偏离的期望增益都有此界，由线性性，$\mathbb{E}[{\hat{\mu }}_T]$ 是上一节误差水平的 CCE。

还可以明确给出实际历史的高概率保证。对条件均值为零、绝对值不超过 $B_i$ 的增量，Azuma–Hoeffding 不等式理路Azuma–Hoeffding 不等式Azuma-Hoeffding inequality · Azuma inequality有界鞅差之和偏离初值的概率具有高斯型指数上界。给出的单侧界为

它来自条件指数矩的迭代界 $\mathbb{E}{e}^{\lambda \sum _t{Z}_{it}}\le e^{T{\lambda }^2{B}_i^2/2}$，再用 Markov 不等式并对 $\lambda$ 优化。因此不要求各轮独立。对 $n$ 位玩家的失败事件应用并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，以至少 $1-\delta$ 的概率，同一次实际历史的经验联合分布是

的 CCE。无需再对 $K_i$ 个比较动作取并集：原势函数界已同时覆盖全部固定动作，而抽样修正是它们共用的一项。

例如循环博弈有 $B_i=2,K_i=3,n=2$。取 $T=10000,\delta =0.05$，分布反馈协议的误差界约为 $0.014823$，实际历史的上述保守高概率界约为 $0.069147$。两个数对应不同输出与反馈协议，不能只因使用同一更新公式就互换。

当 $T$ 预先已知时，令 $\eta \asymp \sqrt{\log N/T}$ 得到最优量级 $O(\sqrt{T\log N})$。未知时域可用 doubling trick 或随时间变化的学习率，但必须重新处理势函数求和；把最终 $T$ 直接代入每一轮并不是在线算法。

同一结构还能把约束满足、零和博弈和 boosting 写成“动作—损失—势函数”的三步循环。矩阵博弈极小极大定理理路矩阵博弈极小极大定理Matrix game minimax theorem · Von Neumann minimax theorem · 有限零和博弈极小极大定理有限二人零和博弈允许独立混合后，行玩家的最大保证收益等于列玩家的最小收益上界，并由一对线性规划提供精确证书。给出零和情形的目标价值与可计算上下界，乘法权重则提供逼近这些界的算法方向。迁移时首先确认反馈是全信息还是 bandit、数值是损失还是收益、范围是否有界，再选择合法更新；元方法复用的是证明结构，不是固定常数。

交换无遗憾算法理路交换无遗憾算法Swap-regret minimization · Blum–Mansour reduction以逐源动作的指数权重学习器和平稳分布构造交换无遗憾算法，证明有限轮界，并把平均乘积分布转成近似相关均衡。把本页指数更新复制到每个源动作，并用平稳分布缩放行反馈；把各行外部遗憾相加后，才得到更强的动作映射比较界。其损失范围缩小到当前源动作概率，因此可保留平方概率和来推导有限轮常数，并在完整分布反馈下构造近似CE。