Playing Large Games with Oracles and AI Debate

我们考虑在动作数量非常多的重复博弈中最小化后悔。这种游戏是通过辩论确保AI安全的设置中固有的，更一般地说，这种游戏的动作是基于语言的。现有的在线游戏算法需要每次迭代计算的次数与动作数量成多项式关系，这对于大型游戏来说可能是禁制性的。 因此，我们考虑基于oracle的算法，因为oracle自然地模拟了对AI代理的访问。通过oracle访问，我们表征了何时可以有效地最小化内部和外部后悔。我们提出了一种新颖的内部后悔最小化的有效算法，其后悔值和每次迭代的计算量对动作数量取对数。 最后，我们通过辩论中的AI安全设置进行实验，展示了我们算法分析的见解的好处。

解决问题：论文旨在解决在具有大量行动的重复博弈中最小化后悔的问题，特别是在AI安全性通过辩论的设置中，以及行动基于语言的博弈中。

关键思路：论文提出了基于Oracle的算法来最小化内部后悔，并证明了在拥有Oracle访问权限的情况下可以高效地最小化内部后悔。作者提出了一种新颖的算法，其后悔和每次迭代的计算都是对数级别的，这是一种高效的算法。

亮点：论文的实验是在AI安全性通过辩论的设置中进行的，展示了算法分析的优势。论文还提到了一些有趣的开放问题，例如如何在没有Oracle访问权限的情况下最小化后悔。

相关研究：最近的相关研究包括“Online Learning with Large Action Sets”和“Efficient Learning in Games with Limited Feedback”。