Playing Large Games with Oracles and AI Debate

我们考虑在具有大量动作的重复博弈中最小化遗憾。这样的游戏在AI安全性通过辩论的设置中是固有的，更一般地说，这些游戏的动作是基于语言的。现有的在线游戏算法需要每次迭代计算动作数量的多项式，这可能会对大型游戏造成限制。因此，我们考虑基于预言机的算法，因为预言机自然地模拟对AI代理的访问。通过预言机访问，我们表征了何时可以高效地最小化内部和外部遗憾。我们提供了一种新颖的高效算法，用于同时最小化外部和内部遗憾，其遗憾依赖于动作数量的对数。我们最后通过AI安全性通过辩论的实验展示了从我们的算法分析中获益的好处。

本文针对具有大量动作的重复博弈中的后悔最小化问题进行研究。这种博弈在AI Safety via Debate的设置中很常见，而且更一般地，这种博弈的动作是基于语言的。现有的在线游戏算法需要多项式计算，这在大型游戏中可能是禁止的。

本文提出了基于Oracle的算法，用于解决内部和外部后悔的最小化问题。通过Oracle访问，我们确定了何时可以有效地最小化内部和外部后悔。我们提出了一种新的高效算法，用于同时最小化外部和内部后悔，其后悔与动作数量的对数成比例。

本文的亮点是提出了一种新的算法来解决具有大量动作的博弈中的后悔最小化问题，并且证明了该算法的效率，其后悔与动作数量的对数成比例。实验结果表明，该算法在AI Safety via Debate的设置中具有潜在的应用价值。

与本文相关的研究包括：《AI Safety via Debate》（Irving等人，2018）等。