Independent learning in stochastic games

DOI10.4171/ICM2022/152arXiv2111.11743OpenAlexW4389775604MaRDI QIDQ6200215FDOQ6200215

Asuman Ozdaglar, Kaiqing Zhang, Muhammed O. Sayin

Publication date: 22 March 2024

Published in: International Congress of Mathematicians (Search for Journal in Brave)

Abstract: Reinforcement learning (RL) has recently achieved tremendous successes in many artificial intelligence applications. Many of the forefront applications of RL involve multiple agents, e.g., playing chess and Go games, autonomous driving, and robotics. Unfortunately, the framework upon which classical RL builds is inappropriate for multi-agent learning, as it assumes an agent's environment is stationary and does not take into account the adaptivity of other agents. In this review paper, we present the model of stochastic games for multi-agent learning in dynamic environments. We focus on the development of simple and independent learning dynamics for stochastic games: each agent is myopic and chooses best-response type actions to other agents' strategy without any coordination with her opponent. There has been limited progress on developing convergent best-response type independent learning dynamics for stochastic games. We present our recently proposed simple and independent learning dynamics that guarantee convergence in zero-sum stochastic games, together with a review of other contemporaneous algorithms for dynamic multi-agent learning in this setting. Along the way, we also reexamine some classical results from both the game theory and RL literature, to situate both the conceptual contributions of our independent learning dynamics, and the mathematical novelties of our analysis. We hope this review paper serves as an impetus for the resurgence of studying independent and natural learning dynamics in game theory, for the more challenging settings with a dynamic environment.

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

zbMATH Keywords

stochastic gamesreinforcement learninglearning in games

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Stochastic games, stochastic differential games (91A15) Rationality and learning in game theory (91A26)

Cites Work

• 10.1162/153244303765208377
• Prediction, Learning, and Games
• Stochastic approximation methods for constrained and unconstrained systems
• Stochastic Games
• \({\mathcal Q}\)-learning
• Stochastic approximation. A dynamical systems viewpoint.
• Learning mixed equilibria
• Title not available (Why is that?)
• Title not available (Why is that?)
• The weighted majority algorithm
• On the rate of convergence of continuous-time fictitious play
• Fictitious play in \(2\times n\) games
• Potential games
• Quantal response equilibria for normal form games
• Online Learning and Online Convex Optimization
• A Theory of Dynamic Oligopoly, I: Overview and Quantity Competition with Large Fixed Costs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Consistency and cautious fictitious play
• Learning in games with strategic complementarities revisited
• Adaptive game playing using multiplicative weights
• A Theory of Dynamic Oligopoly, II: Price Competition, Kinked Demand Curves, and Edgeworth Cycles
• Title not available (Why is that?)
• Fictitious play property for games with identical interests
• An iterative method of solving a game
• Intrinsic robustness of the price of anarchy
• Title not available (Why is that?)
• On the Global Convergence of Stochastic Fictitious Play
• Nash equilibrium and the evolution of preferences
• Asynchronous stochastic approximation and Q-learning
• Stochastic Approximations and Differential Inclusions
• Composable and efficient mechanisms
• Title not available (Why is that?)
• A \(2 \times 2\) game without the fictitious play property
• Distributed dynamic programming
• Adaptive and sophisticated learning in normal form games
• Individual Q-Learning in Normal Form Games
• Best-response dynamics in zero-sum stochastic games
• Fictitious play in one-against-all multi-player games
• A weakened form of fictitious play in two-person zero-sum games
• Multi-agent reinforcement learning: a selective overview of theories and algorithms
• REINFORCEMENT LEARNING IN MARKOVIAN EVOLUTIONARY GAMES
• Asynchronous stochastic approximation with differential inclusions
• Decentralized Q-Learning for Stochastic Teams and Games

This page was built for publication: Independent learning in stochastic games

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