Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization

• URL: http://arxiv.org/abs/2405.02769v1
• Date: Sat, 4 May 2024 22:48:53 GMT
• Title: Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization
• Authors: Youbang Sun, Tao Liu, P. R. Kumar, Shahin Shahrampour,
• Abstract summary: This work focuses on the entropy-regularized independent natural policy gradient (NPG) algorithm in multi-agent reinforcement learning. We show that, under sufficient entropy regularization, the dynamics of this system converge at a linear rate to the quantal response equilibrium (QRE)
• Score: 12.612009339150504
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work focuses on the entropy-regularized independent natural policy gradient (NPG) algorithm in multi-agent reinforcement learning. In this work, agents are assumed to have access to an oracle with exact policy evaluation and seek to maximize their respective independent rewards. Each individual's reward is assumed to depend on the actions of all the agents in the multi-agent system, leading to a game between agents. We assume all agents make decisions under a policy with bounded rationality, which is enforced by the introduction of entropy regularization. In practice, a smaller regularization implies the agents are more rational and behave closer to Nash policies. On the other hand, agents with larger regularization acts more randomly, which ensures more exploration. We show that, under sufficient entropy regularization, the dynamics of this system converge at a linear rate to the quantal response equilibrium (QRE). Although regularization assumptions prevent the QRE from approximating a Nash equilibrium, our findings apply to a wide range of games, including cooperative, potential, and two-player matrix games. We also provide extensive empirical results on multiple games (including Markov games) as a verification of our theoretical analysis.

Related papers

• Independent Policy Mirror Descent for Markov Potential Games: Scaling to Large Number of Players [17.55330497310932]
  Markov Potential Games (MPGs) form an important sub-class of Markov games. MPGs include as a special case the identical-interest setting where all the agents share the same reward function. Scaling the performance of Nash equilibrium learning algorithms to a large number of agents is crucial for multi-agent systems.
  arXiv  Detail & Related papers  (2024-08-15T11:02:05Z)
• Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts [20.8288955218712]
  We propose a framework where a principal guides an agent in a Markov Decision Process (MDP) using a series of contracts. We present and analyze a meta-algorithm that iteratively optimize the policies of the principal and agent. We then scale our algorithm with deep Q-learning and analyze its convergence in the presence of approximation error.
  arXiv  Detail & Related papers  (2024-07-25T14:28:58Z)
• 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)
• On Imperfect Recall in Multi-Agent Influence Diagrams [57.21088266396761]
  Multi-agent influence diagrams (MAIDs) are a popular game-theoretic model based on Bayesian networks. We show how to solve MAIDs with forgetful and absent-minded agents using mixed policies and two types of correlated equilibrium. We also describe applications of MAIDs to Markov games and team situations, where imperfect recall is often unavoidable.
  arXiv  Detail & Related papers  (2023-07-11T07:08:34Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• 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)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  We propose and analyze new fictitious play policy optimization algorithms for zero-sum Markov games with structured but unknown transitions. We prove tight $widetildemathcalO(sqrtK)$ regret bounds after $K$ episodes in a two-agent competitive game scenario. Our algorithms feature a combination of Upper Confidence Bound (UCB)-type optimism and fictitious play under the scope of simultaneous policy optimization.
  arXiv  Detail & Related papers  (2022-07-25T18:29:16Z)
• Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization [28.401280095467015]
  We study the finite-time convergence of independent entropy-regularized natural policy gradient (NPG) methods for potential games. We show that the proposed method converges to the quantal response equilibrium (QRE) at a sublinear rate, which is independent of the size of the action space.
  arXiv  Detail & Related papers  (2022-04-12T01:34:02Z)
• Explore and Control with Adversarial Surprise [78.41972292110967]
  Reinforcement learning (RL) provides a framework for learning goal-directed policies given user-specified rewards. We propose a new unsupervised RL technique based on an adversarial game which pits two policies against each other to compete over the amount of surprise an RL agent experiences. We show that our method leads to the emergence of complex skills by exhibiting clear phase transitions.
  arXiv  Detail & Related papers  (2021-07-12T17:58:40Z)
• Model Free Reinforcement Learning Algorithm for Stationary Mean field Equilibrium for Multiple Types of Agents [43.21120427632336]
  We consider a multi-agent strategic interaction over an infinite horizon where agents can be of multiple types. Each agent has a private state; the state evolves depending on the distribution of the state of the agents of different types and the action of the agent. We show how such kind of interaction can model the cyber attacks among defenders and adversaries.
  arXiv  Detail & Related papers  (2020-12-31T00:12:46Z)
• Calibration of Shared Equilibria in General Sum Partially Observable Markov Games [15.572157454411533]
  We consider a general sum partially observable Markov game where agents of different types share a single policy network. This paper aims at i) formally understanding equilibria reached by such agents, and ii) matching emergent phenomena of such equilibria to real-world targets.
  arXiv  Detail & Related papers  (2020-06-23T15:14:20Z)

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.