RL en Markov Games with Independent Function Approximation: Improved Sample Complexity Bound under the Local Access Model

arXiv:2403.11544v1 Announce Type: new
Abstract: Efficiently learning equilibria with large state and action spaces in general-sum Markov games while overcoming the curse of multi-agency is a challenging problem. Recent works have attempted to solve this problem by employing independent linear function classes to approximate the marginal $Q$-value for each agent. However, existing sample complexity bounds under such a framework have a suboptimal dependency on the desired accuracy $\varepsilon$ or the action space. In this work, we introduce a new algorithm, …

abstract agency approximation arxiv complexity cs.lg equilibria function games general independent linear markov sample solve spaces state type