Efficient Exploration Of Zero-sum Stochastic Games

Abstract

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 stra

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keymartin2020efficient

Related papers

• Solving Discounted Stochastic Two-player Games With Near-optimal Time And Sample Complexity (2019)0.00
• A Generalized Minimax Q-learning Algorithm For Two-player Zero-sum Stochastic Games (2019)9.03
• Approximate Exploitability: Learning A Best Response In Large Games (2020)0.00
• Efficient Episodic Learning Of Nonstationary And Unknown Zero-sum Games Using Expert Game Ensembles (2021)3.58
• Efficient Exploration Via State Marginal Matching (2019)0.00
• Strategically Efficient Exploration In Competitive Multi-agent Reinforcement Learning (2021)0.00
• Probabilistic Insights For Efficient Exploration Strategies In Reinforcement Learning (2025)0.00
• Last-iterate Convergence Of Payoff-based Independent Learning In Zero-sum Stochastic Games (2024)0.00