Robustness and sample complexity of model-based MARL for general-sum Markov games

DOI10.1007/S13235-023-00490-2MaRDI QIDQ6159508zbMATH OpenOpenAlexFDO

Authors Jayakumar Subramanian, Amit K. Sinha, Aditya Mahajan

Publication date 20 June 2023

Published in Dynamic Games and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.02355

Mathematics Subject Classification ID

Markov and semi-Markov decision processes (90C40) Stochastic games, stochastic differential games (91A15) Algorithmic game theory and complexity (91A68)

Abstract: Multi-agent reinforcement learning (MARL) is often modeled using the framework of Markov games (also called stochastic games or dynamic games). Most of the existing literature on MARL concentrates on zero-sum Markov games but is not applicable to general-sum Markov games. It is known that the best-response dynamics in general-sum Markov games are not a contraction. Therefore, different equilibria in general-sum Markov games can have different values. Moreover, the Q-function is not sufficient to completely characterize the equilibrium. Given these challenges, model based learning is an attractive approach for MARL in general-sum Markov games. In this paper, we investigate the fundamental question of emph{sample complexity} for model-based MARL algorithms in general-sum Markov games. We show two results. We first use Hoeffding inequality based bounds to show that $ildemathcalO((1-gamma{)}^{-4}alph{a}^{-2})$ samples per state-action pair are sufficient to obtain a $alpha$-approximate Markov perfect equilibrium with high probability, where $gamma$ is the discount factor, and the $ildemathcalO(cdot)$ notation hides logarithmic terms. We then use Bernstein inequality based bounds to show that $ildemathcalO((1-gamma{)}^{-1}alph{a}^{-2})$ samples are sufficient. To obtain these results, we study the robustness of Markov perfect equilibrium to model approximations. We show that the Markov perfect equilibrium of an approximate (or perturbed) game is always an approximate Markov perfect equilibrium of the original game and provide explicit bounds on the approximation error. We illustrate the results via a numerical example.

Recommendations

• Provably efficient reinforcement learning in decentralized general-sum Markov games
• Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis
• Multi-agent reinforcement learning in common interest and fixed sum stochastic games: an experimental study
• Deep Q-Learning for Nash Equilibria: Nash-DQN
• A multiagent reinforcement learning algorithm with non-linear dynamics

Cites work

• \(H^ \infty\)-optimal control and related minimax design problems. A dynamic game approach.
• A birth–death model of advertising and pricing
• A Theory of Dynamic Oligopoly, I: Overview and Quantity Competition with Large Fixed Costs
• A Theory of Dynamic Oligopoly, II: Price Competition, Kinked Demand Curves, and Edgeworth Cycles
• A theory of regular Markov perfect equilibria in dynamic stochastic games: genericity, stability, and purification
• Approximations in Dynamic Zero-Sum Games I
• Approximations in Dynamic Zero-Sum Games II
• Asymptotic Least Squares Estimators for Dynamic Games
• Dynamic programming and optimal control. Vol. 1.
• Estimating Dynamic Models of Imperfect Competition
• Handbook of dynamic game theory. In 2 volumes
• Hilbert space embeddings and metrics on probability measures
• Homotopy methods to compute equilibria in game theory
• How Does the Value Function of a Markov Decision Process Depend on the Transition Probabilities?
• scientific article; zbMATH DE number 4025193 (Why is no real title available?)
• scientific article; zbMATH DE number 1348599 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 7625165 (Why is no real title available?)
• scientific article; zbMATH DE number 3205836 (Why is no real title available?)
• scientific article; zbMATH DE number 3215739 (Why is no real title available?)
• If multi-agent learning is the answer, what is the question?
• Integral Probability Metrics and Their Generating Classes of Functions
• Lipschitz continuity of value functions in Markovian decision processes
• Markov perfect equilibrium. I: Observable actions
• Markov-Perfect Industry Dynamics: A Framework for Empirical Work
• Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model
• Multi-agent reinforcement learning: a selective overview of theories and algorithms
• Nonlinear programming and stationary equilibria in stochastic games
• On Nonterminating Stochastic Games
• Prediction, Learning, and Games
• Representation and Approximation of Noncooperative Sequential Games
• Robust Markov perfect equilibria
• Sequential Estimation of Dynamic Discrete Games
• Stationary equilibria in stochastic games: structure, selection, and computation
• Stochastic Games

Cited in

(4)

• Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis
• Special issue: multi-agent dynamic decision making and learning
• Provably efficient reinforcement learning in decentralized general-sum Markov games
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium

This page was built for publication: Robustness and sample complexity of model-based MARL for general-sum Markov games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159508)