PAC Reinforcement Learning Algorithm for General-Sum Markov Games

2020/09/05 by Zehfroosh, Ashkan, Tanner, Herbert G.
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2009.02605

Abstract

This paper presents a theoretical framework for probably approximately correct (PAC) multi-agent reinforcement learning (MARL) algorithms for Markov games. The paper offers an extension to the well-known Nash Q-learning algorithm, using the idea of delayed Q-learning, in order to build a new PAC MARL algorithm for general-sum Markov games. In addition to guiding the design of a provably PAC MARL algorithm, the framework enables checking whether an arbitrary MARL algorithm is PAC. Comparative numerical results demonstrate performance and robustness.

Related

• A Hybrid PAC Reinforcement Learning Algorithm
• Robustness and sample complexity of model-based MARL for general-sum Markov games
• Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
• Sample-Efficient Multi-Agent RL: An Optimization Perspective
• Reinforcement Learning With Reward Machines in Stochastic Games