# PAC Reinforcement Learning Algorithm for General-Sum Markov Games

arXiv: https://arxiv.org/abs/2009.02605 · HTML: https://mlsanity.com/paper/2009.02605/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2020.

## Built on by (most cited first, 2 of 2)

- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [Robust PAC Learning of Concurrent Stochastic Games](https://mlsanity.com/paper/2609.04189/) (2026)

## Abstract (arXiv)

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.