交换无遗憾算法

形式陈述 ​

设动作集为 $[m]=\{1,\dots ,m\}$，$m\ge 2$，时域 $T\ge 1$ 已知。每轮先输出概率行向量 $p_t\in {\mathrm{\Delta }}_m$，随后观察完整损失列向量 ${\ell }_t\in [0,1{]}^m$，该轮按混合损失 $p_t{\ell }_t$ 计费。损失可以随已公布的历史与分布变化；本页没有从 $p_t$ 抽一个动作后再把其随机损失冒充混合损失。

交换比较器公理库遗憾与比较器类Regret · Comparator class用累计损失相对预先规定的比较器类最优值来评价在线决策。允许预先规定一个映射 $\varphi :[m]\to [m]$，把原动作 $i$ 的概率质量始终改送到 $\varphi (i)$。混合交换遗憾定义为

$$R_T^{\mathrm{s}\mathrm{w}\mathrm{a}\mathrm{p}}=\underset{\varphi :[m]\to [m]}{max}\sum _{t=1}^T\sum _{i=1}^m{p}_t(i)[{\ell }_t(i)-{\ell }_t(\varphi (i))].$$

映射在比较整段序列时固定，不能每轮重新选。恒等映射始终可选，所以此遗憾非负。下面把 $m$ 个指数乘法权重学习器公理库乘法权重更新方法multiplicative weights update · MWU以指数方式降低高损失动作的权重，并用总权重势函数给出累计性能保证。组合成交换无遗憾算法。

每轮的可执行更新 ​

维护正权重 $w_{t,i,j}$，初始全部为 $1$。行 $i$ 学习“应把源动作 $i$ 的质量转到哪个目标动作 $j$”。取

$$\eta =\sqrt{\frac{8m\log m}{T}}.$$

每轮依次执行：

1. 逐行归一化，$$Q_t(i,j)=\frac{w_{t,i,j}}{\sum _{k=1}^m{w}_{t,i,k}}.$$
2. 解平稳分布方程$$p_t=p_t{Q}_t,\sum _i{p}_t(i)=1,$$并输出 $p_t$。
3. 观察当前完整 ${\ell }_t$，把行 $i$ 的反馈设为$$x_{t,i,j}=p_t(i){\ell }_t(j).$$
4. 更新$$w_{t+1,i,j}=w_{t,i,j}\exp (-\eta p_t(i){\ell }_t(j)).$$

执行 $T$ 轮后结束，返回分布历史和累计混合损失；用于博弈的输出将在后文定义。所有当前损失都在输出 $p_t$ 之后进入更新，因而算法是因果的。只看到一个被选动作的损失时，没有这份完整反馈，不能直接执行本算法。

在精确实数算术中，指数保持所有权重严格为正，故 $Q_t$ 每项为正。实际实现应检查分布归一化、非有限数和求解残差；数值失败应报告状态。有限精度下的近似平稳分布不能无误差地代入下面的恒等式。

平稳分布为何存在且可求 ​

先对任意行随机矩阵 $Q$ 证明存在。取分布 $v$，定义 Cesàro 平均

$$a_N=\frac{1}{N}\sum _{k=0}^{N-1}v{Q}^k.$$

每个 $a_N$ 都在紧致单纯形内，且

$$a_{N}Q-a_N=\frac{v{Q}^N-v}{N}⟶0.$$

取收敛子列，其极限 $p$ 满足 $pQ=p$。对本算法的正矩阵，任一平稳分布的每个坐标也为正。

唯一性也可直接证明。令 $\alpha =\underset{i,j}{min}Q(i,j)>0$。若 $m\alpha =1$，$Q$ 每行均匀，结论直接成立；否则写成

$$Q=m\alpha U+(1-m\alpha )S,$$

其中 $U$ 每行均匀，$S$ 为行随机矩阵。对两个分布 $p,r$，有 $(p-r)U=0$，而行随机矩阵不增行向量的 $1$-范数，因此

$$\Vert (p-r)Q{\Vert }_1\le (1-m\alpha )\Vert p-r{\Vert }_1.$$

两个平稳分布代入后只能相同。求解时可把 $(Q^{\mathsf{T}}-I)p^{\mathsf{T}}=0$ 的一个冗余方程换成总和为一，再用线性方程求解公理库Gaussian 消元与 LU 分解Gaussian elimination · LU factorization · PA equals LU把 Gaussian 消元保存为可复用的带置换 LU 分解，再用三角求解处理一个或多个右端。得到该唯一分布。这里没有要求把 $Q$ 的幂一直迭代到某个未经证明的固定次数。

正确性：从行遗憾到交换遗憾 ​

记第 $i$ 行学习器的实际混合损失与固定目标比较损失为

$$L_i=\sum _t{p}_t(i)\sum _j{Q}_t(i,j){\ell }_t(j),C_{i,j}=\sum _t{p}_t(i){\ell }_t(j),$$

并令 $r_i=L_i-\underset{j}{min}{C}_{i,j}$。平稳性给出

$$\sum _i{L}_i=\sum _t{p}_t{Q}_t{\ell }_t=\sum _t{p}_t{\ell }_t.$$

映射 $\varphi$ 对各源动作的选择互不约束，所以

$$R_T^{\mathrm{s}\mathrm{w}\mathrm{a}\mathrm{p}}=\sum _t{p}_t{\ell }_t-\sum _i\underset{j}{min}{C}_{i,j}=\sum _i{r}_i.$$

个别 $r_i$ 可以为负，这不妨碍总和非负。若不使用 $p_t(i)$ 缩放行反馈，$C_{i,j}$ 就不再表示把源动作 $i$ 的质量送给目标 $j$ 的费用，归约的账本会失效。

有限轮界：保留每行的实际损失范围 ​

行 $i$ 的反馈范围是 $[0,p_t(i)]$。对总权重 $W_{t,i}=\sum _j{w}_{t,i,j}$，使用Hoeffding 指数矩引理公理库Azuma–Hoeffding 不等式Azuma-Hoeffding inequality · Azuma inequality有界鞅差之和偏离初值的概率具有高斯型指数上界。的区间长度版本，得

$$\log \frac{W_{t+1,i}}{W_{t,i}}\le -\eta p_t(i)\sum _j{Q}_t(i,j){\ell }_t(j)+\frac{{\eta }^2{p}_t(i{)}^2}{8}.$$

这里把 $j$ 按当前行分布抽取只是一个有限加权和的记法；不需要假设损失序列独立。另一方面，任意比较目标 $j$ 的权重给出

$$W_{T+1,i}\ge e^{-\eta C_{i,j}},W_{1,i}=m.$$

上下界合并后，

$$r_i\le \frac{\log m}{\eta }+\frac{\eta }{8}\sum _t{p}_t(i{)}^2.$$

对行求和，并使用 $\sum _i{p}_t(i{)}^2\le 1$，得到

$$R_T^{\mathrm{s}\mathrm{w}\mathrm{a}\mathrm{p}}\le \frac{m\log m}{\eta }+\frac{\eta T}{8}=\sqrt{\frac{mT\log m}{2}}.$$

指数更新对任意 $\eta >0$ 都保持正权重，无需线性乘法因子版本的步长限制。若只把每行的范围粗略写成 $[0,1]$，会丢掉上述平方概率和，得到更弱的动作数因子。本页常数由这段缩放后的势函数计算直接得出。

直觉

每个源动作都雇一个“替换建议员”，它长期比较应该把这部分概率送给谁。各行建议拼成矩阵 $Q_t$，但直接平均这些建议不能让费用自动对齐。选择 $p_t=p_t{Q}_t$，意味着“按 $p_t$ 直接选目标”和“先按 $p_t$ 选源，再照该行建议选目标”产生同一分布。

于是学习器真实费用恰好等于各行费用之和。每行只需竞争一个固定目标动作，所有行各自竞争成功，就覆盖了全部固定动作映射。

例子与边界

两动作、三轮的完整更新 ​

取 $\eta =\log 4$，这是为账本选择的固定学习率，不是本例时域的最优选择。损失依次为

$${\ell }_1=(1,0{)}^{\mathsf{T}},{\ell }_2=(0,1{)}^{\mathsf{T}},{\ell }_3=(1,0{)}^{\mathsf{T}}.$$

令 $a=1/(1+2^{1/3})\approx 0.4424933340$，各轮状态为：

轮次	$Q_t$ 的两行	平稳分布 $p_t$	两行反馈
$1$	$(1/2,1/2)$；$(1/2,1/2)$	$(1/2,1/2)$	$(1/2,0)$；$(1/2,0)$
$2$	$(1/3,2/3)$；$(1/3,2/3)$	$(1/3,2/3)$	$(0,1/3)$；$(0,2/3)$
$3$	$(a,1-a)$；$(1-a,a)$	$(1/2,1/2)$	$(1/2,0)$；$(1/2,0)$

第一轮后两行权重都是 $(1/2,1)$。第二轮后分别为

$$w_{3,1}=(1/2,2^{-2/3}),w_{3,2}=(1/2,2^{-4/3}),$$

归一化就得到表中的对称矩阵。第三轮后两行第一项再减半，分别为 $(1/4,2^{-2/3})$ 和 $(1/4,2^{-4/3})$。

总混合损失为 $1/2+2/3+1/2=5/3$，源动作加权后的固定目标损失为

$$(C_{i,j})=\left(\begin{array}{cc}1& 1/3\\ 1& 2/3\end{array}\right).$$

两行都更愿意始终改送动作 $2$，所以交换遗憾为

$$R_3^{\mathrm{s}\mathrm{w}\mathrm{a}\mathrm{p}}=\frac{5}{3}-(\frac{1}{3}+\frac{2}{3})=\frac{2}{3}.$$

也可从行损失核对：

$$r_1=\frac{5}{36}+\frac{a}{2},r_2=\frac{19}{36}-\frac{a}{2},r_1+r_2=\frac{2}{3}.$$

这份账本同时验证了行概率、加权反馈、平稳性和遗憾相加，不能只检查最终权重归一化。

计算模型与近似求解 ​

保存权重需 $O(m^2)$ 空间，逐轮归一化及更新有 $O(m^2)$ 个条目；用稠密消元求平稳分布的常规成本为每轮 $O(m^3)$ 次实数算术。指数函数计算、有限精度表示及生成完整损失反馈应另计。精确正性不等于浮点实现永不下溢。

若使用一个近似分布 ${\tilde{p}}_t$，则真实混合费用与行费用之差是 $({\tilde{p}}_t-{\tilde{p}}_t{Q}_t){\ell }_t$。即使其余指数更新仍精确，也需把这项累计误差加回证明；仅声称“求解器收敛了”不够。没有混合速度分析时，简单幂迭代也不能承诺统一次数内达到所需精度。

$m=1$ 时直接选唯一动作，交换遗憾为零。未知时域可以在长度翻倍的阶段中重置全部权重，按各阶段预算选择学习率；各阶段的最优映射可能不同，但全程固定映射的遗憾不超过阶段最大遗憾之和，几何求和保持 $O(\sqrt{mT\log m})$ 量级。

推论与应用

从分布反馈到相关均衡 ​

在有限博弈中，玩家 $i$ 有 $K_i$ 个动作，收益范围为 $[a_i,b_i]$，$B_i=b_i-a_i>0$。每轮各玩家先提交分布 $p_i^t$，然后得到面对对手当轮乘积分布的完整期望收益向量

$$g_i^t(a)=\sum _{s_{-i}}(\prod _{j\ne i}{p}_j^t(s_j))u_i(a,s_{-i}).$$

每人用损失 ${\ell }_i^t(a)=(b_i-g_i^t(a))/B_i$ 运行本算法。输出各轮乘积分布的平均

$${\bar{\mu }}_T(s)=\frac{1}{T}\sum _{t=1}^T\prod _i{p}_i^t(s_i).$$

对相关均衡公理库相关均衡Correlated equilibrium · CE允许玩家根据私人动作建议选择偏离，以有限条线性服从约束刻画联合分布的稳定性。的每条未归一化建议偏离 $a\to b$，代入并求和得到

$$D_i(a\to b;{\bar{\mu }}_T)=\frac{B_i}{T}\sum _t{p}_i^t(a)[{\ell }_i^t(a)-{\ell }_i^t(b)]\le B_i\sqrt{\frac{K_i\log K_i}{2T}}.$$

最后一步选择只把 $a$ 改成 $b$、其他动作不变的映射。故该输出是确定性的 ${\epsilon }_T$-CE，其中

$${\epsilon }_T=\underset{i}{max}{B}_i\sqrt{\frac{K_i\log K_i}{2T}}.$$

实际上同一界还控制每个完整映射的总偏离增益。常收益或只有一个动作的玩家偏离增益为零，无需除以零或调用多动作更新。

可以通过“先均匀选一轮，再按该轮各玩家分布独立抽取”实现输出；共享轮次会产生相关性。这一般不是平均边际的乘积，也不保证最后一轮成为 Nash 均衡。若每轮只实际抽取一个行动剖面，得到的是另一份随机经验分布，必须另行分析抽样误差，不能把上面的确定性结论原样搬过去。

普通外部无遗憾与同一分布反馈协议给出CCE公理库粗相关均衡Coarse correlated equilibrium · CCE对联合动作分布检验事先固定的单方偏离，并把经验分布的约束违反量精确写成平均外部遗憾。，本算法增加源动作相关的比较器，才得到 CE。生成完整期望反馈本身可能需要枚举大量对手剖面；每个学习器的多项式更新成本不会消除收益表访问成本。

参考资料

• Avrim Blum and Yishay Mansour, “From External to Internal Regret”, Journal of Machine Learning Research 8, 2007, pp. 1307–1324，§3、Theorem 5 的平稳分布归约与 Corollary 7 的量级。本页对指数更新另用缩放 Hoeffding 界给出显式常数。
• Gabriele Farina, Learning in Games: Φ-Regret Minimization, MIT 6.S890, Fall 2024, Lecture 8，§1、Theorem 1.1 与平均乘积策略的解释；讲义采用列向量约定。