Oct, 2023
从外部到 Swap Regret 2.0：大动作空间的高效减少和无视敌对
From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich
TL;DR我们提供了一种新颖的从交换后悔最小化到外部后悔最小化的约简方法，该方法改进了 Blum-Mansour 和 Stolz-Lugosi 的经典约简，不需要动作空间的有限性。我们的结果表明，只要存在某个假设类的无外部后悔算法，同样必然存在该类别的无交换后悔算法。对于使用专家建议的学习问题，我们的结果表明，在 log (N)^{O (1/ε)} 轮迭代中并且每次迭代的复杂度为 O (N)，可以保证交换后悔受到 ε 的约束，而 Blum-Mansour 和 Stolz-Lugosi 的经典约简则需要 O (N/ε^2) 轮迭代和至少 Ω(N^2) 的复杂度。我们的结果还带有一个相关的下界，与 [BM07] 中的下界相反，该下界适用于具有遗忘性和限制的 κ1 的对手和学习者，以及可以使用专家分布的情况，从而说明轮数必须是 Ω(N/ε^2) 或以指数的方式与 1/ε 成反比。我们的约简意味着，如果在某个游戏中可以进行无后悔学习，那么该游戏必须具有近似的相关均衡，具有任意好的近似程度。这加强了无后悔学习所暗示的粗略相互相关均衡的存在。重要的是，它提供了一种存在相关均衡的充分条件，大大扩展了行动集有限的要求，从而回答了 [DG22; Ass+23] 中未解决的问题。此外，它还回答了关于均衡计算和 / 或游戏学习的几个未解决问题。