Efficient exploration of zero-sum stochastic games
This addresses the challenge of efficient exploration in costly simulation-based games, such as financial or military applications, but is incremental as it adapts existing methods to a new game-solving context.
The paper tackles the problem of learning strategies with low exploitability in zero-sum stochastic games when only oracle access is available and evaluations are costly, showing that Thompson sampling and Bayes-UCB outperform other exploration strategies in this setting.
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.