遗憾与比较器类

遗憾把整段序列压成一场赛后对账：算法必须在信息逐轮到达时行动，比较器却可以看完整段序列后从预先声明的集合中挑最好者。这个“事后挑、但只能在固定集合里挑”的不对称既让基准有解释力，又避免它强到每轮都预知答案。

遗憾是加性差，不是近似比理路近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。或竞争比；“$O(\sqrt{T})$”也只有在动作集、反馈模型、损失范围与比较器明确时才完整。错误数可视为 0–1 损失累计值，但 mistake bound 在可实现序列上与零错误比较器比较，是更强的专门模型。

No-regret 的含义是平均每轮落后量的上界消失，而不是累计损失趋零，也不是最后一次动作收敛。算法完全可能和一个很差的最好比较器一起承受巨大绝对损失；它保证的是没有长期落后于这个参照类，而不是保证环境本身容易预测。

固定专家与动态 oracle ​

设两位专家在十轮中的累计损失分别为 3 和 7，算法累计损失为 4，则相对最好固定专家的遗憾为 $4-3=1$，不是错误数 4，也不是相对每轮事后最好建议的差。若每轮轮流有一位专家零损失，动态 oracle 可累计为零，而任何固定专家约损失五次；换比较器会彻底改变问题难度。

bandit 中的两层期望 ​

令 $L_T$ 是学习器累计损失，$L_{T,i}$ 是同一实际损失表上固定臂 $i$ 的累计损失。无论随机 bandit 还是非预见自适应对手，都应区分

因为 $\mathbb{E}\underset{i}{min}{L}_{T,i}\le \underset{i}{min}\mathbb{E}{L}_{T,i}$，有 ${\overline{R}}_T\le \mathbb{E}[{\mathrm{Reg}}_T]$。例如一轮两臂的损失表以各 $1/2$ 概率为 $(0,1)$ 或 $(1,0)$，独立均匀抽臂时 $\mathbb{E}{L}_T=1/2$，所以 ${\overline{R}}_T=0$，而 $\mathbb{E}[{\mathrm{Reg}}_T]=1/2$。确定的 oblivious 表使两个指标相等；随机表不自动如此。这里都在实际表上比较，不涉及改变过去动作后对手会怎样反应的 policy regret。

负遗憾与更强比较器 ​

遗憾还可能线性为负。让两动作的损失依次重复 $(0,1),(1,0)$，学习器按事先规定的奇偶轮交替选第一、第二动作；当 $T$ 为偶数时，它的总损失为 $0$，每个固定动作的总损失都是 $T/2$，所以遗憾为 $-T/2$。这条路径上平均遗憾并未趋零，却完全符合“不长期落后于最好固定动作”的目标。No-regret 因此应读作次线性上界，而不是强制遗憾的绝对值次线性。若想保证对每个区间或每个切换次数受限的比较器都好，需要 strongly adaptive 或 shifting regret，并为比较器的额外自由支付复杂度。

根据自己的动作改换比较器 ​

重复博弈中，外部比较器说“所有轮次都改选固定 $b$”；内部比较器说“只把原先选 $a$ 的轮次改成 $b$”；交换比较器则允许给每个原动作指定一个替代动作 $\varphi (a)$。后两者使用了学习器原动作的信息，比较器类更强，普通固定动作遗憾界不能自动覆盖它们。

这种区别恰好决定经验联合分布满足哪种均衡：粗相关均衡理路粗相关均衡Coarse correlated equilibrium · CCE对联合动作分布检验事先固定的单方偏离，并把经验分布的约束违反量精确写成平均外部遗憾。的固定偏离违反量等于外部遗憾除以轮数，相关均衡理路相关均衡Correlated equilibrium · CE允许玩家根据私人动作建议选择偏离，以有限条线性服从约束刻画联合分布的稳定性。的单对服从约束则等于相应内部遗憾除以轮数。例如三轮双方都依次选 $0,1,2$ 的循环博弈历史，最佳固定动作总收益与实际收益同为零，但每次把原动作循环加一能累计多得 $3$。前者没有外部遗憾，后者仍有交换遗憾；不是同一个保证的两种名称。

从总遗憾上界到平均表现上界只需除以 $T$：若 ${\mathrm{Reg}}_T\le C\sqrt{T}$，则 ${\mathrm{Reg}}_T/T\le C/\sqrt{T}\to 0$；实际差值可以更低。但这不意味着最后一轮动作收敛，也不保证单轮损失下降；在线到批转换通常要平均迭代点或随机抽取一轮，并另外使用凸性或随机顺序假设。

当 $\mathcal{U}$ 是有限专家集合时，定义直接导向专家建议预测理路专家建议预测Prediction with expert advice在全信息反馈下组合多个专家，并与事后最好的固定专家比较。：指数权重用 $O(\sqrt{T\log |\mathcal{U}|})$ 的代价同时追踪所有固定专家。若 $\mathcal{U}$ 是凸集，在线凸优化理路在线凸优化Online convex optimization · OCO每轮先在凸域选点、再承受未知凸损失，并与最好固定点比较。把同一比较式与梯度几何结合；若允许有限次切换，则需把切换位置与次数的复杂度加入界中。

遗憾界还可通过在线到批转换产生随机样本下的风险保证。转换不是字面上把 $T$ 改成样本量：必须说明数据次序、损失凸性以及输出采用平均迭代点还是随机一轮，才能把因果序列上的平均比较转成总体期望风险。

交换无遗憾的平稳分布归约理路交换无遗憾算法Swap-regret minimization · Blum–Mansour reduction以逐源动作的指数权重学习器和平稳分布构造交换无遗憾算法，证明有限轮界，并把平均乘积分布转成近似相关均衡。为上述更强比较器提供实际算法。每个源动作的学习器选择一个固定替代目标，平稳性将这些费用与真实混合损失对齐；三轮算例给出交换遗憾2/3，而不是把普通外部遗憾界直接改名。