Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
In this paper, we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with discount factor $\gamma\in(0,1)$ we provide an algorithm that computes an $\epsilon$-optimal strategy with high-probability given $\tilde{O}((1 - \gamma)^{-3} \epsilon^{-2})$ samples from the transition function for each state-action-pair. Our algorithm runs in time nearly linear in the number of samples and uses space nearly linear in the number of state-action pairs. As stochastic games generalize Markov decision processes (MDPs) our runtime and sample complexities are optimal due to Azar et al (2013). We achieve our results by showing how to generalize a near-optimal Q-learning based algorithms for MDP, in particular Sidford et al (2018), to two-player strategy computation algorithms. This overcomes limitations of standard Q-learning and strategy iteration or alternating minimization based approaches and we hope will pave the way for future reinforcement learning results by facilitating the extension of MDP results to multi-agent settings with little loss.
Code (0)
등록된 구현이 없습니다.
Tasks
Q-LearningReinforcement LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Link between Sequential Semi-anonymous Nonatomic Games and their Large Finite Counterparts
We show that equilibria of a sequential semi-anonymous nonatomic game (SSNG) can be adopted by players in corresponding large but finite dynamic games to achieve near-equilibrium payoffs. Such equilibria in the form of r…
FormSoft-Bellman Equilibrium in Affine Markov Games: Forward Solutions and Inverse Learning
Markov games model interactions among multiple players in a stochastic, dynamic environment. Each player in a Markov game maximizes its expected total discounted reward, which depends upon the policies of the other playe…
OpenAI GymDecentralized model-free reinforcement learning in stochastic games with average-reward objective
We propose the first model-free algorithm that achieves low regret performance for decentralized learning in two-player zero-sum tabular stochastic games with infinite-horizon average-reward objective. In decentralized l…
Q-Learningreinforcement-learningReinforcement Learning (RL)Parallel Algorithm for Approximating Nash Equilibrium in Multiplayer Stochastic Games with Application to Naval Strategic Planning
Many real-world domains contain multiple agents behaving strategically with probabilistic transitions and uncertain (potentially infinite) duration. Such settings can be modeled as stochastic games. While algorithms have…
Gap-Dependent Bounds for Two-Player Markov Games
As one of the most popular methods in the field of reinforcement learning, Q-learning has received increasing attention. Recently, there have been more theoretical works on the regret bound of algorithms that belong to t…
Q-LearningVocal Bursts Valence Prediction