Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games

• URL: http://arxiv.org/abs/2502.09780v1
• Date: Thu, 13 Feb 2025 21:28:51 GMT
• Title: Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games
• Authors: Tong Yang, Bo Dai, Lin Xiao, Yuejie Chi,
• Abstract summary: Multi-agent reinforcement learning (MARL) lies at the heart of a plethora of applications involving the interaction of a group of agents in a shared unknown environment. We propose a novel model-based algorithm, called VMG, that incentivizes exploration via biasing the empirical estimate of the model parameters.
• Score: 40.05960121330012
• License:
• Abstract: Multi-agent reinforcement learning (MARL) lies at the heart of a plethora of applications involving the interaction of a group of agents in a shared unknown environment. A prominent framework for studying MARL is Markov games, with the goal of finding various notions of equilibria in a sample-efficient manner, such as the Nash equilibrium (NE) and the coarse correlated equilibrium (CCE). However, existing sample-efficient approaches either require tailored uncertainty estimation under function approximation, or careful coordination of the players. In this paper, we propose a novel model-based algorithm, called VMG, that incentivizes exploration via biasing the empirical estimate of the model parameters towards those with a higher collective best-response values of all the players when fixing the other players' policies, thus encouraging the policy to deviate from its current equilibrium for more exploration. VMG is oblivious to different forms of function approximation, and permits simultaneous and uncoupled policy updates of all players. Theoretically, we also establish that VMG achieves a near-optimal regret for finding both the NEs of two-player zero-sum Markov games and CCEs of multi-player general-sum Markov games under linear function approximation in an online environment, which nearly match their counterparts with sophisticated uncertainty quantification.

Related papers

• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
  We show that a model-free stage-based Q-learning algorithm can enjoy the same optimality in the $H$ dependence as model-based algorithms. Our algorithm features a key novel design of updating the reference value functions as the pair of optimistic and pessimistic value functions.
  arXiv  Detail & Related papers  (2023-08-17T08:34:58Z)
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation [56.715186432566576]
  We propose a new model, independent linear Markov game, for reinforcement learning with a large state space and a large number of agents. We design new algorithms for learning correlated equilibria (CCE) and Markov correlated equilibria (CE) with sample bounds complexity that only scalely with each agent's own function class complexity. Our algorithms rely on two key technical innovations: (1) utilizing policy replay to tackle non-stationarity incurred by multiple agents and the use of function approximation; and (2) separating learning Markov equilibria and exploration in the Markov games.
  arXiv  Detail & Related papers  (2023-02-07T18:47:48Z)
• Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
  We study offline multi-agent reinforcement learning (RL) in Markov games. We provide the first framework for sample-efficient offline learning in Markov games.
  arXiv  Detail & Related papers  (2023-02-06T05:22:27Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  This paper focuses on the most basic setting of competitive multi-agent RL, namely two-player zero-sum Markov games. We propose a single-loop policy optimization method with symmetric updates from both agents, where the policy is updated via the entropy-regularized optimistic multiplicative weights update (OMWU) method. Our convergence results improve upon the best known complexities, and lead to a better understanding of policy optimization in competitive Markov games.
  arXiv  Detail & Related papers  (2022-10-03T16:05:43Z)
• Pareto Actor-Critic for Equilibrium Selection in Multi-Agent Reinforcement Learning [18.20664209675016]
  This work focuses on equilibrium selection in no-conflict multi-agent games. Pareto Actor-Critic (Pareto-AC) is an actor-critic algorithm that maximises the returns of all agents.
  arXiv  Detail & Related papers  (2022-09-28T18:14:34Z)
• Efficient Model-based Multi-agent Reinforcement Learning via Optimistic Equilibrium Computation [93.52573037053449]
  H-MARL (Hallucinated Multi-Agent Reinforcement Learning) learns successful equilibrium policies after a few interactions with the environment. We demonstrate our approach experimentally on an autonomous driving simulation benchmark.
  arXiv  Detail & Related papers  (2022-03-14T17:24:03Z)
• Non-cooperative Multi-agent Systems with Exploring Agents [10.736626320566707]
  We develop a prescriptive model of multi-agent behavior using Markov games. We focus on models in which the agents play "exploration but near optimum strategies"
  arXiv  Detail & Related papers  (2020-05-25T19:34:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.