下一个词元预测和遗憾最小化

我们考虑如何在对抗性在线决策环境中采用下一个词元预测算法的问题。具体来说，如果我们在对手动作序列上的分布 $\mathcal{D}$ 上训练下一个词元预测模型，那么什么时候诱导的在线决策算法（通过对模型的预测做出近似最佳响应）具有较低的对抗性遗憾（即，什么时候 $\mathcal{D}$ 是 \emph{低遗憾分布}）？对于无界上下文窗口（模型做出的预测可以取决于对手迄今为止采取的所有行动），我们表明，尽管并非每个分布 $\mathcal{D}$ 都是低遗憾分布，但每个分布 $\mathcal{D}$ 都指数地接近（在电视距离中）一个低遗憾分布，因此始终可以以相对于原始下一个标记预测模型的准确性而言可忽略不计的成本实现次线性遗憾。与此相反，对于有界上下文窗口（其中模型做出的预测只能取决于对手过去采取的 $w$ 动作，就像现代 Transformer 架构中的情况一样），我们表明对手游戏的一些分布 $\mathcal{D}$ 是 $θ(1)$ - 远离任何低遗憾分布 $\mathcal{D'}$ （即使当 $w = Ω(T)$ 等时存在分布）。最后，我们通过证明无界上下文鲁棒性过程可以通过标准 Transformer 架构的层来实现来补充这些结果，并提供经验证据证明 Transformer 模型可以被有效地训练来表示这些新的低遗憾分布。