Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall

Abstract

We study the problem of learning a Nash equilibrium (NE) in an imperfect information game (IIG) through self-play. Precisely, we focus on two-player, zero-sum, episodic, tabular IIG under the perfect-recall assumption where the only feedback is realizations of the game (bandit feedback). In particular, the dynamic of the IIG is not known -- we can only access it by sampling or interacting with a game simulator. For this learning setting, we provide the Implicit Exploration Online Mirror Descent (IXOMD) algorithm. It is a model-free algorithm with a high-probability bound on the convergence rate to the NE of order $1/\sqrt{T}$ where $T$ is the number of played games. Moreover, IXOMD is computationally efficient as it needs to perform the updates only along the sampled trajectory.

arXiv comment20 pages

References in corpus (9)

• Efficient learning by implicit exploration in bandit problems with side observations
• Provable Self-Play Algorithms for Competitive Reinforcement Learning
• Online Convex Optimization in Adversarial Markov Decision Processes
• Solving Large Imperfect Information Games Using CFR+
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions
• Solving Large Sequential Games with the Excessive Gap Technique
• Near-Optimal Reinforcement Learning with Self-Play
• Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games