Playing Large Games with Oracles and AI Debate
This addresses computational efficiency challenges in large-scale game settings like AI safety and language-based games, though it is incremental as it builds on existing regret minimization frameworks.
The paper tackles the problem of regret minimization in repeated games with a large number of actions, such as those in AI Safety via Debate, by proposing an oracle-based algorithm that achieves regret logarithmic in the number of actions.
We consider regret minimization in repeated games with a very large number of actions. Such games are inherent in the setting of AI Safety via Debate \cite{irving2018ai}, and more generally games whose actions are language-based. Existing algorithms for online game playing require per-iteration computation polynomial in the number of actions, which can be prohibitive for large games. We thus consider oracle-based algorithms, as oracles naturally model access to AI agents. With oracle access, we characterize when internal and external regret can be minimized efficiently. We give a novel efficient algorithm for simultaneous external and internal regret minimization whose regret depends logarithmically on the number of actions. We conclude with experiments in the setting of AI Safety via Debate that shows the benefit of insights from our algorithmic analysis.