乘法权重更新方法

元方法而非单一算法 ​

乘法权重描述一种可复用结构：维护非负权重，把它们归一化为分布，观察反馈后按每个动作的损失成比例缩放。专家建议、某些 boosting、零和博弈和近似线性规划都可出现这套结构，但反馈范围、收益或损失符号不同，对应的更新和常数也不同。

指数损失版本 ​

对 $N$ 个动作，初始 $w_{1,i}=1$。第 $t$ 轮使用

$$p_{t,i}=\frac{w_{t,i}}{W_t},W_t=\sum _j{w}_{t,j},$$

并在观察 ${\ell }_{t,i}\in [0,1]$ 后更新

$$w_{t+1,i}=w_{t,i}{e}^{-\eta {\ell }_{t,i}}.$$

这里 $p_t$ 是概率分布，$\eta >0$ 是学习率。若实际只观察被选动作的损失，就不能直接使用全信息版本，必须构造估计量。

势函数推导 ​

从上方看，Hoeffding 引理给

$$\log \frac{W_{t+1}}{W_t}=\log {\mathbb{E}}_{i\sim p_t}{e}^{-\eta {\ell }_{t,i}}\le -\eta ⟨p_t,{\ell }_t⟩+\frac{{\eta }^2}{8}.$$

求和后得到 $\log W_{T+1}\le \log N-\eta L_A+{\eta }^{2}T/8$，其中 $L_A=\sum _t⟨p_t,{\ell }_t⟩$。从下方看，对任意固定动作 $i$，

$$W_{T+1}\ge w_{T+1,i}=e^{-\eta L_i}.$$

合并两式便有

$$L_A-L_i\le \frac{\log N}{\eta }+\frac{\eta T}{8}.$$

这就是指数势函数的上下夹逼；取 $\eta \asymp \sqrt{\log N/T}$ 得 $O(\sqrt{T\log N})$ regret。

线性化版本与范围 ​

有些文献采用 $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用数据结构状态势能的变化修正实际成本以界定均摊成本。在这里跟踪总权重的指数增长，而算法分析中的摊还势能通常比较单次真实成本，目的不同。不是任何“把数乘到权重上”的启发式都继承上述定理。

参考资料

• Sanjeev Arora, Elad Hazan, Satyen Kale, The Multiplicative Weights Update Method: A Meta-Algorithm and Applications, Theory of Computing, 2012.
• Nicolò Cesa-Bianchi, Gábor Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006.