  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.
