Independent Reinforcement Learning in Discounted Markov Games

arXiv:2609.00504 · cs.GT, cs.AI, cs.LG, cs.SY, eess.SY, math.OC · Submitted 2026-09-01 · Read on arXiv

cs.GT, cs.AI, cs.LG, cs.SY, eess.SY, math.OC

Submitted: 2026-09-01

Updated: 2026-09-01

Comments: 54 pages, 3 figures

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Regret — 73× in this paper · explained in 3 episodes
• Reinforcement Learning — 20× in this paper · explained in 4 episodes
• Nash Equilibrium — 9× in this paper · explained in 2 episodes
• Q-learning — 7× in this paper · explained in 3 episodes
• Accuracy — 6× in this paper · explained in 1 episode
• Benchmark — 6× in this paper · explained in 2 episodes
• International Conference on Machine Learning — 4× in this paper
• Convergence Guarantees — 3× in this paper · explained in 3 episodes
• Decentralized Learning — 3× in this paper · explained in 2 episodes
• Action Space — 2× in this paper · explained in 1 episode
• Adam — 2× in this paper · explained in 2 episodes
• In International Conference on Learning Representations — 2× in this paper
• Layered Optimistic Online Mirror Descent — 2× in this paper
• Sample Complexity — 2× in this paper · explained in 15 episodes
• Adaptive Algorithm — 1× in this paper · explained in 1 episode
• Cooperation — 1× in this paper · explained in 2 episodes
• Distribution Shift — 1× in this paper · explained in 5 episodes
• Generalization — 1× in this paper · explained in 13 episodes
• Multi-Agent Reinforcement Learning (MARL) — 1× in this paper · explained in 4 episodes
• Multi-Agent System — 1× in this paper · explained in 5 episodes
• Non-stationarity — 1× in this paper · explained in 2 episodes
• Objective Function — 1× in this paper · explained in 2 episodes
• Thirty Fourth Conference on Learning Theory — 1× in this paper

Sources

• Regret Minimization and Convergence to Equilibria in General-sum Markov Games
• Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games
• Near Optimal Convergence to Coarse Correlated Equilibrium in General-Sum Markov Games
• Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis

Related papers

• Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
• In-Context Credit Assignment via the Core
• Optimal Regret for Online Market Making with Limit Order Book
• Breaking 1/epsilon Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
• Enhancing Affine Maximizer Auctions with Correlation-Aware Payment
• LLM Bidders Preserve the Mechanism-Level Orderings of Human Bidders