Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games
| Autor: | Weichao Mao, Tamer Başar |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Statistics and Probability Economics and Econometrics Computer Science - Machine Learning Computer Science - Artificial Intelligence Applied Mathematics Computer Graphics and Computer-Aided Design Machine Learning (cs.LG) Computer Science Applications Computational Mathematics Artificial Intelligence (cs.AI) Computational Theory and Mathematics Computer Science - Multiagent Systems Multiagent Systems (cs.MA) |
| Popis: | This paper addresses the problem of learning an equilibrium efficiently in general-sum Markov games through decentralized multi-agent reinforcement learning. Given the fundamental difficulty of calculating a Nash equilibrium (NE), we instead aim at finding a coarse correlated equilibrium (CCE), a solution concept that generalizes NE by allowing possible correlations among the agents' strategies. We propose an algorithm in which each agent independently runs optimistic V-learning (a variant of Q-learning) to efficiently explore the unknown environment, while using a stabilized online mirror descent (OMD) subroutine for policy updates. We show that the agents can find an $\epsilon$-approximate CCE in at most $\widetilde{O}( H^6S A /\epsilon^2)$ episodes, where $S$ is the number of states, $A$ is the size of the largest individual action space, and $H$ is the length of an episode. This appears to be the first sample complexity result for learning in generic general-sum Markov games. Our results rely on a novel investigation of an anytime high-probability regret bound for OMD with a dynamic learning rate and weighted regret, which would be of independent interest. One key feature of our algorithm is that it is fully \emph{decentralized}, in the sense that each agent has access to only its local information, and is completely oblivious to the presence of others. This way, our algorithm can readily scale up to an arbitrary number of agents, without suffering from the exponential dependence on the number of agents. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|