  In many game settings, the game is not explicitly given but is only
accessible by playing it. While there have been impressive demonstrations in
such settings, prior techniques have not offered safety guarantees, that is,
guarantees on the game-theoretic exploitability of the computed strategies. In
this paper we introduce an approach that shows that it is possible to provide
exploitability guarantees in such settings without ever exploring the entire
game. We introduce a notion of a certificate of an extensive-form approximate
Nash equilibrium. For verifying a certificate, we give an algorithm that runs
in time linear in the size of the certificate rather than the size of the whole
game. In zero-sum games, we further show that an optimal certificate -- given
the exploration so far -- can be computed with any standard game-solving
algorithm (e.g., using a linear program or counterfactual regret minimization).
However, unlike in the cases of normal form or perfect information, we show
that certain families of extensive-form games do not have small approximate
certificates, even after making extremely nice assumptions on the structure of
the game. Despite this difficulty, we find experimentally that very small
certificates, even exact ones, often exist in large and even in infinite games.
Overall, our approach enables one to try one's favorite exploration strategies
while offering exploitability guarantees, thereby decoupling the exploration
strategy from the equilibrium-finding process.
