PAC Reinforcement Learning Algorithm for General-Sum Markov Games

2020-09-05 · Ashkan Zehfroosh, Herbert G. Tanner

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.

📄 PDF Abstract BibTeX arXiv:2009.02605

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement LearningQ-Learningreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

A Sharp Analysis of Model-based Reinforcement Learning with Self-Play

2020-10-04 · Qinghua Liu, Tiancheng Yu, Yu Bai, Chi Jin

Model-based algorithms -- algorithms that explore the environment through building and utilizing an estimated model -- are widely used in reinforcement learning practice and theoretically shown to achieve optimal sample …

Model-based Reinforcement Learning Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning+1

Extended Markov Games to Learn Multiple Tasks in Multi-Agent Reinforcement Learning

2020-02-14 · Borja G. León, Francesco Belardinelli

The combination of Formal Methods with Reinforcement Learning (RL) has recently attracted interest as a way for single-agent RL to learn multiple-task specifications. In this paper we extend this convergence to multi-age…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Data Poisoning to Fake a Nash Equilibrium in Markov Games

2023-06-13 · Young Wu, Jeremy McMahan, Xiaojin Zhu, Qiaomin Xie

We characterize offline data poisoning attacks on Multi-Agent Reinforcement Learning (MARL), where an attacker may change a data set in an attempt to install a (potentially fictitious) unique Markov-perfect Nash equilibr…

Data Poisoning Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning

Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?

2021-12-27 · Han Zhong, Zhuoran Yang, Zhaoran Wang, Michael I. Jordan

We study multi-player general-sum Markov games with one of the players designated as the leader and the other players regarded as followers. In particular, we focus on the class of games where the followers are myopic, i…

Reinforcement Learning (RL)

Can Reinforcement Learning Efficiently Find Stackelberg-Nash Equilibria in General-Sum Markov Games?

2021-09-29 · Han Zhong, Zhuoran Yang, Zhaoran Wang, Michael Jordan

We study multi-player general-sum Markov games with one of the players designated as the leader and the rest regarded as the followers. In particular, we focus on the class of games where the state transitions are only d…