指数权重与 Hedge

协议与算法 ​

第 $t$ 轮开始时，每个专家已有累计损失 $L_{t-1,i}=\sum _{s<t}{\ell }_{s,i}$。Hedge 取

$$p_{t,i}=\frac{e^{-\eta L_{t-1,i}}}{\sum _j{e}^{-\eta L_{t-1,j}}},$$

随后承受混合损失 ${\hat{\ell }}_t=\sum _i{p}_{t,i}{\ell }_{t,i}$，并观察完整向量 ${\ell }_t\in [0,1{]}^N$。分布只使用过去损失；把当前未知 ${\ell }_t$ 放入 $p_t$ 会偷看答案。

Regret 证明 ​

令 $W_t=\sum _i{e}^{-\eta L_{t-1,i}}$。由 $[0,1]$ 变量的 Hoeffding lemma，

$$\log \frac{W_{t+1}}{W_t}=\log \sum _i{p}_{t,i}{e}^{-\eta {\ell }_{t,i}}\le -\eta {\hat{\ell }}_t+\frac{{\eta }^2}{8}.$$

求和给 $\log W_{T+1}\le \log N-\eta \sum _t{\hat{\ell }}_t+{\eta }^{2}T/8$。另一方面，对最佳专家 $i^{\ast }$，$\log W_{T+1}\ge -\eta L_{T,i^{\ast }}$。因此

$${\mathrm{Reg}}_T=\sum _t{\hat{\ell }}_t-\underset{i}{min}{L}_{T,i}\le \frac{\log N}{\eta }+\frac{\eta T}{8}.$$

知道时域 $T$ 时取 $\eta =\sqrt{8\log N/T}$，得到 $\sqrt{T\log N/2}$；未知 $T$ 可用递减学习率或 doubling，而不能把优化后的固定 $\eta$ 当作任意时域通用值。

概率预测例子 ​

多个天气模型各自给出明日降雨概率。只要采用一个共同的有界评分损失，Hedge 会根据累计表现形成混合分布，不必永久选定单一模型。若使用 log loss，专家报出零概率而事件发生会造成无穷损失；必须截断概率或使用专门的 mixability 分析，标准 $[0,1]$ 证明不能直接套用。

边界与关系 ​

Hedge 需要全损失反馈。只观察所选臂时，需重要性加权估计公理库赌博机重要性加权估计importance-weighted bandit estimator · inverse propensity estimator把单个被选臂的反馈放大为完整损失向量的条件无偏估计。，方差项也会改变。Weighted Majority公理库Weighted Majority 算法Weighted Majority · 加权多数算法在二元在线预测中，对犯错专家乘法降权并按剩余权重多数表决。按二元错误乘固定因子并作多数表决；本页处理一般有界损失和混合损失。MWU公理库乘法权重更新方法multiplicative weights update · MWU以指数方式降低高损失动作的权重，并用总权重势函数给出累计性能保证。则抽象这类更新供其他问题复用。

参考资料

• Yoav Freund, Robert E. Schapire, A Decision-Theoretic Generalization of On-Line Learning, 1997.
• Nicolò Cesa-Bianchi, Gábor Lugosi, Prediction, Learning, and Games, Cambridge University Press, 2006.