PaperlayerView exact revision on arXiv

Source-linked AI summary

Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games

Stefanos Leonardos, Will Overman, Ioannis Panageas, Georgios Piliouras

arXiv:2106.01969v4cs.LGcs.GT

TL;DR

The paper asks whether potential-game coordination and convergence guarantees extend from normal-form games to state-dependent multi-agent reinforcement learning. It defines Markov Potential Games, proves deterministic Nash policies exist, and shows independent policy gradient reaches approximate Nash policies with polynomial iteration complexity, while noting unresolved limitations and open directions.

  • Problem

    Multi-agent reinforcement learning has limited theoretical convergence guarantees, especially for cooperative settings beyond the restricted zero-sum results studied previously.

  • Method

    The paper defines Markov Potential Games through a state-dependent potential and adapts agent-wise gradient-dominance arguments from single-agent policy-gradient analysis.

  • Results

    Independent policy gradient reaches an ϵ-approximate Nash policy in O(1/ϵ2) iterations, while finite-sample stochastic policy gradient does so in O(1/ϵ5) iterations.

  • Takeaways & Limitations

    MPGs retain deterministic Nash policies and polynomial-time convergence guarantees even when state-games need not all be potential games.

  • Takeaways & Limitations

    The analysis does not derive the higher-moment gradient-estimator bounds needed for logarithmic dependence on the failure probability, and several extensions remain open.

Abstract

from arXiv · show

Potential games are arguably one of the most important and widely studied classes of normal form games. They define the archetypal setting of multi-agent coordination as all agent utilities are perfectly aligned with each other via a common potential function. Can this intuitive framework be transplanted in the setting of Markov Games? What are the similarities and differences between multi-agent coordination with and without state dependence? We present a novel definition of Markov Potential Games (MPG) that generalizes prior attempts at capturing complex stateful multi-agent coordination. Counter-intuitively, insights from normal-form potential games do not carry over as MPGs can consist of settings where state-games can be zero-sum games. In the opposite direction, Markov games where every state-game is a potential game are not necessarily MPGs. Nevertheless, MPGs showcase standard desirable properties such as the existence of deterministic Nash policies. In our main technical result, we prove fast convergence of independent policy gradient to Nash policies by adapting recent gradient dominance property arguments developed for single agent MDPs to multi-agent learning settings.

1 Introduction

The paper introduces Markov Potential Games (MPGs) to study convergence in multi-agent reinforcement learning, where theoretical guarantees remain limited despite practical advances. It shows that independent policy gradient converges to approximate Nash policies and establishes structural properties distinguishing MPGs from state-wise potential games.

  • Markov Potential Games: MPGs generalize normal-form potential games to multi-agent Markov decision processes through a state-dependent potential function.A unilateral policy change changes an agent’s value by the corresponding change in the potential, while weighted and ordinal variants are also considered.
  • Convergence guarantees: O(1/ϵ2) iterations suffice for independent direct-parameterized policy gradient to reach an ϵ-Nash policy with simultaneous updates.The result applies to n-agent MPGs under the stated direct parameterization.
  • Convergence guarantees: O(1/ϵ5) iterations suffice for the finite-sample stochastic policy-gradient analogue to reach an ϵ-Nash policy.The stochastic result uses greedy parameterization with simultaneous independent updates.
  • Structural properties: MPGs can contain state-games that are zero-sum, whereas Markov games whose every state-game is a potential game need not be MPGs.The paper also provides sufficient conditions involving action-independent transitions or regularity across state rewards.
  • Proof strategy: The convergence proof adapts single-agent gradient-dominance arguments by showing agent-wise gradient dominance along each agent’s policy direction.The paper handles exact and finite-sample gradients through independent policy updates and projected stochastic gradient ascent.
  • Relation to prior work: Prior MPG definitions mainly focus on state-based potential MDPs and impose restrictive conditions, while this work studies a broader class of stateful coordination settings.The paper emphasizes that action-dependent rewards and transitions create the main structural challenge.

2 Preliminaries

The paper formalizes multi-agent MDPs, policies, value functions, Nash policies, and Markov Potential Games, then describes independent policy-gradient learning under direct parameterization and exploration.

  • Markov Decision Process: An MDP consists of finite states, agent action and reward spaces, transition probabilities, an initial-state distribution, and a shared discount factor.
  • Markov Decision Process: Agents observe the current state, choose actions, receive individual rewards, and transition according to the action-dependent dynamics.
  • Markov Potential Games: A Markov Potential Game has a state-dependent potential whose change matches each agent’s value change when that agent alone changes policy.
  • Markov Potential Games: In an MPG, each agent’s value decomposes into a common potential term and a dummy term independent of that agent’s policy.
  • Independent Policy Gradient: Independent policy gradient uses local rewards, actions, and environmental observations, with direct policy parameterization and projected gradient updates.
  • Independent Policy Gradient: Alpha-greedy exploration provides unbiased gradient estimates with bounded variance, while changing policies make independent learning analytically challenging.

3 Structural Properties of Markov Potential Games

MPGs retain deterministic Nash policies, but statewise potential structure alone is insufficient: state preferences and action-dependent transitions can break the global potential property, while broader cross-state structure can restore it.

  • Deterministic Nash Policies: MPGs possess a Nash policy profile that is deterministic for every agent.
  • Deterministic Nash Policies: The proof iteratively replaces agents’ randomized components with deterministic optimal policies while preserving the Nash-profile property.
  • Limits of Statewise Potentiality: Statewise potential games need not be MPGs: conflicting state preferences can produce an overall competitive MDP without a deterministic Nash policy.
  • Limits of Statewise Potentiality: Even cooperative statewise potential games can lack an exact global potential when transitions depend on agents’ actions, although they may be ordinal MPGs.
  • Sufficient Conditions: Sufficient conditions for statewise potentiality to imply an MPG are agent-independent transitions or equality of individual dummy terms across states.
  • Cross-State Structure: An MPG may contain a non-potential, constant-sum state when a larger group of states jointly admits a potential function.

4 Convergence of Policy Gradient in Markov Potential Games

This section establishes convergence of projected and stochastic policy gradient to approximate Nash policies in Markov Potential Games, using potential-function smoothness and agent-wise gradient dominance. It also identifies scope limits for ordinal MPGs and high-probability guarantees.

  • Potential-based convergence: Independent policy gradient in an MPG is equivalent to gradient ascent on the potential function because each agent’s value and the potential have matching policy derivatives.This equivalence lets the analysis transfer single-agent gradient arguments to the multi-agent potential.
  • Potential-based convergence: An ϵ-stationary point of the potential function is an ϵ-approximate Nash policy.The result follows because no agent can improve its value substantially through a feasible unilateral policy direction.
  • Potential-based convergence: An agent-wise stationary point of its value is a best response to the fixed policies of the other agents.Fixing the other agents turns the decision problem into a single-agent MDP, enabling gradient domination arguments.
  • Exact gradients: Independent projected policy gradient reaches an ϵ-approximate Nash policy within the iteration bound specified by Theorem 4.5, from arbitrary initialization.The proof uses smoothness of the potential, with Amax denoting the largest action-set size across agents.
  • Stochastic gradients: Projected stochastic policy gradient reaches an ϵ-approximate Nash policy in expectation within the iteration bound specified by Theorem 4.7.The stochastic result uses α-greedy parametrization with α = ϵ.
  • Scope and limitations: The analysis does not provide the desired logarithmic dependence on failure probability for single-trajectory stochastic gradients, and ordinal MPGs lack a smoothness bound needed for convergence rates.For ordinal MPGs, the paper establishes asymptotic convergence to Nash policies when the potential is differentiable, but not finite-time rates.

5 Experiments: Congestion Games

The experiment studies policy gradient in a two-state, four-facility congestion MDP with eight agents. Across equal and heterogeneous learning rates, the algorithm reaches the expected deterministic Nash profile, with larger heterogeneous step-sizes producing faster convergence.

  • Experimental setup: The experiment uses N = 8 agents, four facilities, and two states: a safe state and a distancing state.Each state is a congestion game in which agents prefer facilities with more agents.
  • Results: The converged Nash policy is deterministic, and heterogeneous learning rates produce faster convergence while preserving qualitatively equivalent results.The comparison uses L1-accuracy trajectories over 10 runs for equal and different learning rates.
  • Experimental setup: More than N/2 agents at one facility triggers the distancing state, while returning to the safe state requires at most N/4 agents per facility.The transitions are deterministic in the main experiment, with probabilistic transitions reported as quantitatively equivalent.
  • Experimental setup: The runs compare a common learning rate of 0.0001 with agent-specific learning rates randomly sampled in [.00005, 0.0005].The agents estimate gradients from mini-batches of size 20 with γ = 0.99.
  • Results: All runs learn the expected Nash profile: equal allocation among the two preferred facilities in the safe state and two agents per facility in the distancing state.The safe-state allocation maximizes utility and avoids transition to the distancing state.

6 Further Discussion and Conclusions

The paper establishes positive structural and algorithmic results for MPGs, while identifying equilibrium selection, broader algorithms, and extensions beyond MPGs as open directions.

  • Deterministic Nash policies always exist, and independent policy gradient converges polynomially fast to a Nash policy profile with finite samples.These are the paper’s principal structural and algorithmic guarantees.
  • Open questions: Price-of-Anarchy analysis remains an open question for Markov Potential Games and more general Markov Games.The proposed direction concerns inefficiency from lacking centralized coordination.
  • Open questions: Equilibrium-selection results for deterministic policies would require techniques beyond standard Lyapunov arguments, such as the Center-Stable-Manifold theorem.The paper points to convergence toward particular deterministic equilibria as a future direction.
  • Open questions: Extending softmax parametrization and Natural Policy Gradient guarantees from single-agent MDPs to multi-agent MPGs is a natural direction for future work.The cited single-agent results include asymptotic, polynomial, and dimension-free convergence under different methods or regularization.
  • Open questions: Whether strong convergence guarantees extend from MPGs to more general classes of Markov games remains open.The paper describes its MPG results as orthogonal to existing work on Markov zero-sum games.
  • Open questions: Future work may also seek regularities beyond equilibration, including cyclic or recurrent orbits, invariant functions, or social-welfare guarantees.The paper notes that universal practical convergence guarantees are unlikely even in more restricted normal-form games.

A Additional Notation and Definitions: Section 2

This section introduces notation for value, Q-value, advantage, and discounted state-visitation functions used in the paper’s proofs.

  • The value function V^i_s gives agent i’s expected reward from starting state s under the joint policy.
  • Q-value and Advantage Functions: Q-value and advantage functions are introduced as additional objects for the proof notation.The supplied passages identify these definitions but do not include their complete formulas.
  • The initial-state value is obtained by taking the expected state value under the initial distribution ρ.
  • Discounted State Distribution: The discounted state-visitation distribution d^π_s0 records the state distribution induced by a joint policy, with an analogous version averaged over ρ.

B Omitted Materials: Section 3

The omitted material characterizes MPGs through value-function separability and derivative equality, then uses these properties to establish deterministic Nash policies and sufficient MPG conditions.

  • P2 states that each agent’s value-function derivatives coincide with the corresponding derivatives of the potential.
  • P1 characterizes MPGs by decomposing each agent’s value into a common potential term and an agent-specific dummy term independent of that agent’s policy.
  • A global maximizer of the potential is converted into a deterministic Nash policy by repeatedly replacing randomized individual policies with deterministic optimal policies.Each replacement preserves the potential maximum and reduces the number of randomized policies.
  • The proof handles action-dependent transitions by showing that the transition-induced term is either independent of the agent’s policy or common across agents.
  • Theorem 3.2 derives MPGs when transitions are action-independent or when the stated C2 regularity conditions hold.In both cases, the value function separates into a common potential component and a dummy component.

B.1 Examples

The examples demonstrate that statewise potential structure is not necessary for an MPG, while policy-dependent transitions can make the MPG property difficult to determine.

  • In the first example, a constant-sum state game is not an ordinal potential game, yet the resulting MDP is an ordinal MPG.A direct calculation gives Φ_s = ϕ_s for both states.
  • The construction reverses the agents’ effective roles across states, allowing an MPG despite the non-potential state game.The paper notes that analogous constructions can use state aliasing or stochastic transitions.
  • The example’s joined rewards over the initial state and successor state admit a potential function equal to the sum of agents’ rewards.
  • When p0 depends on the agents’ policies, determining whether an exact potential exists is not immediate.
  • When the transition probability p0 is constant with respect to policies, the value functions have a form that supports the potential-game analysis.
  • The construction extends to both episodic and continuing settings after removing the discount scaling factor for finite horizons.

C Omitted Materials: Section 4

This section develops the multi-agent performance-difference and smoothness arguments underlying policy-gradient convergence in Markov Potential Games.

  • The proof uses a multi-agent Performance Difference Lemma to relate policy changes to value differences.
  • The MPG structure equates each agent’s policy gradient with the corresponding gradient of the potential function.
  • The Hessian analysis bounds block matrices and uses spectral-norm arguments to establish smoothness of the potential.
  • The proof separately analyzes single-agent and cross-agent policy perturbations before combining the resulting derivative bounds.
  • Direct policy parameterization makes transition probabilities linear in each agent’s policy along one-agent perturbations, simplifying derivative bounds.

D Auxiliary Lemmas

The auxiliary lemmas establish projected-gradient and stochastic-gradient properties needed to analyze optimization of the MPG potential.

  • Projection-based gradient lemmas characterize updates for smooth functions over the policy simplex.
  • The potential function is treated as smooth, with a Lipschitz gradient bound used in the projected-gradient analysis.
  • The stochastic policy-gradient estimator is unbiased for each agent’s utility gradient and has bounded variance.
  • The auxiliary results also record the connection between the agents’ gradients and the potential-gradient structure.

E Additional Experiments

Additional experiments test independent policy gradient under asymmetric rewards, larger populations and action sets, and stochastic transitions.

  • Coordination beyond MPGs: More iterations are required under asymmetric facility shifts, but independent policy gradient still reaches the same Nash policy as in the symmetric setting.
  • Coordination with more agents and facilities: With N = 16 agents and 5 facilities, all runs converge to optimal Nash policies sharing the same optimal facility distribution.
  • Coordination with random transitions: Under stochastic transitions, independent policy gradient converges to deterministic Nash policies in both tested cases.
  • Coordination with random transitions: Higher transition randomness leaves the algorithm at an ϵ-Nash policy for many iterations, consistent with the theoretical predictions.
Loading 2106.01969v4…