English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We propose a new model, independent linear Markov game, for multi-agentreinforcement learning with a large state space and a large number of agents.This is a class of Markov games with independent linear function approximation,where each agent has its own function approximation for the state-action valuefunctions that are marginalized by other players' policies. We design newalgorithms for learning the Markov coarse correlated equilibria (CCE) andMarkov correlated equilibria (CE) with sample complexity bounds that only scalepolynomially with each agent's own function class complexity, thus breaking thecurse of multiagents. In contrast, existing works for Markov games withfunction approximation have sample complexity bounds scale with the size of the\emph{joint action space} when specialized to the canonical tabular Markov gamesetting, which is exponentially large in the number of agents. Our algorithmsrely on two key technical innovations: (1) utilizing policy replay to tacklenon-stationarity incurred by multiple agents and the use of functionapproximation; (2) separating learning Markov equilibria and exploration in theMarkov games, which allows us to use the full-information no-regret learningoracle instead of the stronger bandit-feedback no-regret learning oracle usedin the tabular setting. Furthermore, we propose an iterative-best-response typealgorithm that can learn pure Markov Nash equilibria in independent linearMarkov potential games. In the tabular case, by adapting the policy replaymechanism for independent linear Markov games, we propose an algorithm with$\widetilde{O}(\epsilon^{-2})$ sample complexity to learn Markov CCE, whichimproves the state-of-the-art result $\widetilde{O}(\epsilon^{-3})$ inDaskalakis et al. 2022, where $\epsilon$ is the desired accuracy, and alsosignificantly improves other problem parameters.

Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation