PAC Reinforcement Learning Algorithm for General-Sum Markov Games

Area of Science:

• Artificial Intelligence
• Machine Learning
• Game Theory

Background:

• Multi-agent reinforcement learning (MARL) is crucial for complex decision-making.
• Markov games are standard models for strategic interactions.
• Existing MARL algorithms often lack theoretical performance guarantees.

Purpose of the Study:

• To develop a theoretical framework for probably approximately correct (PAC) MARL algorithms.
• To introduce a novel PAC MARL algorithm for general-sum Markov games.
• To provide a method for verifying the PAC property of MARL algorithms.

Main Methods:

• Extension of Nash Q-learning using delayed Q-learning principles.
• Development of a theoretical PAC framework for MARL.
• Comparative numerical simulations to evaluate algorithm performance.

Main Results:

• A new PAC MARL algorithm for general-sum Markov games is proposed.
• The theoretical framework allows for PAC verification of MARL algorithms.
• Numerical results validate the algorithm's performance and robustness.

Conclusions:

• The proposed framework advances PAC MARL theory.
• The novel algorithm offers provable PAC guarantees.
• The framework facilitates the design and analysis of reliable MARL systems.