  We investigate the increasingly important and common game-solving setting
where we do not have an explicit description of the game but only oracle access
to it through gameplay, such as in financial or military simulations and
computer games. During a limited-duration learning phase, the algorithm can
control the actions of both players in order to try to learn the game and how
to play it well. After that, the algorithm has to produce a strategy that has
low exploitability. Our motivation is to quickly learn strategies that have low
exploitability in situations where evaluating the payoffs of a queried strategy
profile is costly. For the stochastic game setting, we propose using the
distribution of state-action value functions induced by a belief distribution
over possible environments. We compare the performance of various exploration
strategies for this task, including generalizations of Thompson sampling and
Bayes-UCB to this new setting. These two consistently outperform other
strategies.
