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.

Stats

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

Related papers

• Local And Adaptive Mirror Descents In Extensive-form Games (2023)0.00
• Model-based Reinforcement Learning For Offline Zero-sum Markov Games (2022)0.00
• Score-based Equilibrium Learning In Multi-player Finite Games With Imperfect Information (2023)0.00
• Generalized Bandit Regret Minimizer Framework In Imperfect Information Extensive-form Game (2022)0.00
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning From Offline Datasets (2022)0.00
• Sample-efficient Reinforcement Learning Of Partially Observable Markov Games (2022)0.00
• Efficient Episodic Learning Of Nonstationary And Unknown Zero-sum Games Using Expert Game Ensembles (2021)3.58
• Playing Markov Games Without Observing Payoffs (2025)0.00