FTSG Exploration.pdf

Exploration-exploitation trade-off in multi-player stochastic games, where players aim to find an approximate Nash Equilibrium (NE).

Proposed Framework: Upper Bounding the Values for Players (UBVP), which guides exploration in finite-horizon turn-based stochastic games (FTSGs) by leveraging the key insight that players choose optimal policies conditioning on the policies of others.

Key Contributions:

1. UBVP Framework: A novel framework for exploration in FTSGs, which applies the Optimism in the Face of Uncertainty (OFU) principle to converge to the best responses of each player.
2. Non-Asymptotic Analysis: A non-asymptotic analysis of UBVP, showing that it can efficiently explore the unknown environment and converge to a subgame perfect equilibrium (SPE).
3. Concrete Algorithms: Two concrete algorithms based on UBVP: Uniform-PAC with a sample complexity of ˜O(1/ε^2) and a high-probability exploitability bound of ˜O(√T).

Related Work: The work relates to Markov Decision Processes (MDPs), stochastic games, and extensive games, with a focus on exploration-exploitation trade-offs and Nash Equilibrium.

Empirical Results: The proposed method performs well compared to state-of-the-art exploration methods for stochastic games and extensive games, approaching the SPE in a designed cooperative game while other methods are trapped in sub-optimal NEs.