Towards General Function Approximation In Zero-sum Markov Games

Abstract

This paper considers two-player zero-sum finite-horizon Markov games with simultaneous moves. The study focuses on the challenging settings where the value function or the model is parameterized by general function classes. Provably efficient algorithms for both decoupled and \{coordinated\} settings are developed. In the \{decoupled\} setting where the agent controls a single player and plays against an arbitrary opponent, we propose a new model-free algorithm. The sample complexity is governed by the Minimax Eluder dimension -- a new dimension of the function class in Markov games. As a special case, this method improves the state-of-the-art algorithm by a \(\sqrt\{d\}\) factor in the regret when the reward function and transition kernel are parameterized with \(d\)-dimensional linear features. In the \{coordinated\} setting where both players are controlled by the agent, we propose a model-based algorithm and a model-free algorithm. In the model-based algorithm, we prove that sample

Stats

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

Related papers

• A Generalized Minimax Q-learning Algorithm For Two-player Zero-sum Stochastic Games (2019)9.03
• Improving Sample Efficiency Of Model-free Algorithms For Zero-sum Markov Games (2023)0.00
• Two-timescale Q-learning With Function Approximation In Zero-sum Stochastic Games (2023)0.00
• Posterior Sampling For Competitive RL: Function Approximation And Partial Observation (2023)0.00
• Learning Two-player Mixture Markov Games: Kernel Function Approximation And Correlated Equilibrium (2022)0.00
• Refined Sample Complexity For Markov Games With Independent Linear Function Approximation (2024)0.00
• A New Policy Iteration Algorithm For Reinforcement Learning In Zero-sum Markov Games (2023)0.00
• Model-based Reinforcement Learning For Offline Zero-sum Markov Games (2022)0.00