Feature-Based Q-Learning for Two-Player Stochastic Games

Abstract

Consider a two-player zero-sum stochastic game where the transition function can be embedded in a given feature space. We propose a two-player Q-learning algorithm for approximating the Nash equilibrium strategy via sampling. The algorithm is shown to find an $\epsilon$-optimal strategy using sample size linear to the number of features. To further improve its sample efficiency, we develop an accelerated algorithm by adopting techniques such as variance reduction, monotonicity preservation and two-sided strategy approximation. We prove that the algorithm is guaranteed to find an $\epsilon$-optimal strategy using no more than $\tilde{\mathcal{O}}(K/({\epsilon }^2(1-\gamma {)}^4))$ samples with high probability, where $K$ is the number of features and $\gamma$ is a discount factor. The sample, time and space complexities of the algorithm are independent of original dimensions of the game.

23 pages

References in corpus (3)

• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• A Theoretical Analysis of Deep Q-Learning
• Scalable Bilinear $\pi$ Learning Using State and Action Features

Cited by in corpus (14)

• Game-Theoretic Multiagent Reinforcement Learning
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Near-Optimal Reinforcement Learning with Self-Play
• V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
• The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces
• Minimax Sample Complexity for Turn-based Stochastic Game
• Towards General Function Approximation in Zero-Sum Markov Games
• On Reinforcement Learning for Turn-based Zero-sum Markov Games
• Online Learning in Unknown Markov Games
• Gap-Dependent Bounds for Two-Player Markov Games