Independent Learning in Stochastic Games
summary
Claim: a small modification of independent Q‑learning — decentralized Q‑learning with a two-time-scale update and smooth best responses — provably converges to Markov stationary Nash equilibria in infinite‑horizon zero‑sum and identical‑interest stochastic games under standard reachability and step‑size conditions. The algorithm is symmetric, payoff‑based and rational (it best‑responds to a converged opponent); it fails for general‑sum games, shows convergence in simple simulations, and extension to deep function approximation remains open.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:49Background
- 2:38A Foundational & Intriguing Question
- 3:23Is Finding Equilibrium all We Need/Have Got?
- 6:11On the other Hand, in Multi-agent RL..
- 10:26Question of Interest
- 11:59Solution Concept: (Markov Stationary) Nash Equilibrium
- 14:24Decentralized Q-learning Dynamics
- 21:44Features of the Learning Dynamics
- 23:24Convergence Guarantees: Zero-sum Stochastic Games
- 24:08Rationality Guarantees
- 26:36Convergence Analysis
- 29:38Numerical Example
- 29:54Fictitious-play Property and Game agnostic Convergence
- 32:20What about Infinite-horizon General-sum Cases?
- 34:10Concluding Remarks
related talks
47mRebel: Combining Deep Reinforcement Learning and Search for Imperfect-Information Games
45mAGT and Machine Learning
32mMulti-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"?
42mRethinking AI Alignment and Evaluation under Heterogeneous Preferences
41mSpotlight Talks
01h 03mIEEE CoG 2019 - Industry Day - David Silver (DeepMind)
41mTheory of Modern AI: Learning Theoretic, Game Theoretic, and Algorithmic Perspectives
48mLearning by Local Entropy Maximization