Why do Policy Gradient Methods work so nicely in Cooperative MARL? Evidence from Policy Representation

In cooperative multi-agent reinforcement studying (MARL), because of its on-policy nature, coverage gradient (PG) strategies are sometimes believed to be much less pattern environment friendly than worth decomposition (VD) strategies, that are off-policy. However, some current empirical research display that with correct enter illustration and hyper-parameter tuning, multi-agent PG can obtain surprisingly sturdy efficiency in comparison with off-policy VD strategies.

Why may PG strategies work so nicely? In this put up, we are going to current concrete evaluation to point out that in sure eventualities, e.g., environments with a extremely multi-modal reward panorama, VD could be problematic and result in undesired outcomes. By distinction, PG strategies with particular person insurance policies can converge to an optimum coverage in these circumstances. In addition, PG strategies with auto-regressive (AR) insurance policies can study multi-modal insurance policies.

Figure 1: totally different coverage illustration for the 4-player permutation recreation.

CTDE in Cooperative MARL: VD and PG strategies

Centralized coaching and decentralized execution (CTDE) is a well-liked framework in cooperative MARL. It leverages world data for more practical coaching whereas retaining the illustration of particular person insurance policies for testing. CTDE could be carried out by way of worth decomposition (VD) or coverage gradient (PG), main to 2 several types of algorithms.

VD strategies study native Q networks and a mixing operate that mixes the native Q networks to a worldwide Q operate. The mixing operate is normally enforced to fulfill the Individual-Global-Max (IGM) precept, which ensures the optimum joint motion could be computed by greedily selecting the optimum motion domestically for every agent.

By distinction, PG strategies straight apply coverage gradient to study a person coverage and a centralized worth operate for every agent. The worth operate takes as its enter the worldwide state (e.g., MAPPO) or the concatenation of all of the native observations (e.g., MADDPG), for an correct world worth estimate.

The permutation recreation: a easy counterexample the place VD fails

We begin our evaluation by contemplating a stateless cooperative recreation, specifically the permutation recreation. In an -player permutation recreation, every agent can output actions . Agents obtain reward if their actions are mutually totally different, i.e., the joint motion is a permutation over ; in any other case, they obtain reward. Note that there are symmetric optimum methods on this recreation.

Figure 2: the 4-player permutation recreation.

Let us concentrate on the 2-player permutation recreation for our dialogue. In this setting, if we apply VD to the sport, the worldwide Q-value will factorize to

the place and are native Q-functions, is the worldwide Q-function, and is the blending operate that, as required by VD strategies, satisfies the IGM precept.

Figure 3: high-level instinct on why VD fails within the 2-player permutation recreation.

We formally show that VD can not symbolize the payoff of the 2-player permutation recreation by contradiction. If VD strategies had been capable of symbolize the payoff, we might have

However, if both of those two brokers have totally different native Q values, e.g. , then in response to the IGM precept, we will need to have

Otherwise, if and , then

As a outcome, worth decomposition can not symbolize the payoff matrix of the 2-player permutation recreation.

What about PG strategies? Individual insurance policies can certainly symbolize an optimum coverage for the permutation recreation. Moreover, stochastic gradient descent can assure PG to converge to one in every of these optima below delicate assumptions. This means that, though PG strategies are much less widespread in MARL in contrast with VD strategies, they are often preferable in sure circumstances which might be frequent in real-world functions, e.g., video games with a number of technique modalities.

We additionally comment that within the permutation recreation, as a way to symbolize an optimum joint coverage, every agent should select distinct actions. Consequently, a profitable implementation of PG should be sure that the insurance policies are agent-specific. This could be performed through the use of both particular person insurance policies with unshared parameters (known as PG-Ind in our paper), or an agent-ID conditioned coverage (PG-ID).

PG outperform greatest VD strategies on widespread MARL testbeds

Going past the easy illustrative instance of the permutation recreation, we lengthen our research to widespread and extra life like MARL benchmarks. In addition to StarCraft Multi-Agent Challenge (SMAC), the place the effectiveness of PG and agent-conditioned coverage enter has been verified, we present new ends in Google Research Football (GRF) and multi-player Hanabi Challenge.

Figure 4: (high) profitable charges of PG strategies on GRF; (backside) greatest and common analysis scores on Hanabi-Full.

In GRF, PG strategies outperform the state-of-the-art VD baseline (CDS) in 5 eventualities. Interestingly, we additionally discover that particular person insurance policies (PG-Ind) with out parameter sharing obtain comparable, generally even increased profitable charges, in comparison with agent-specific insurance policies (PG-ID) in all 5 eventualities. We consider PG-ID within the full-scale Hanabi recreation with various numbers of gamers (2-5 gamers) and examine them to SAD, a robust off-policy Q-learning variant in Hanabi, and Value Decomposition Networks (VDN). As demonstrated within the above desk, PG-ID is ready to produce outcomes similar to or higher than the most effective and common rewards achieved by SAD and VDN with various numbers of gamers utilizing the identical variety of setting steps.

Beyond increased rewards: studying multi-modal habits by way of auto-regressive coverage modeling

Besides studying increased rewards, we additionally research the way to study multi-modal insurance policies in cooperative MARL. Let’s return to the permutation recreation. Although we have now proved that PG can successfully study an optimum coverage, the technique mode that it lastly reaches can extremely rely upon the coverage initialization. Thus, a pure query shall be:

Can we study a single coverage that may cowl all of the optimum modes?

In the decentralized PG formulation, the factorized illustration of a joint coverage can solely symbolize one specific mode. Therefore, we suggest an enhanced approach to parameterize the insurance policies for stronger expressiveness — the auto-regressive (AR) insurance policies.

Figure 5: comparability between particular person insurance policies (PG) and auto-regressive insurance policies (AR) within the 4-player permutation recreation.

Formally, we factorize the joint coverage of brokers into the type of

the place the motion produced by agent relies upon by itself statement and all of the actions from earlier brokers . The auto-regressive factorization can symbolize any joint coverage in a centralized MDP. The solely modification to every agent’s coverage is the enter dimension, which is barely enlarged by together with earlier actions; and the output dimension of every agent’s coverage stays unchanged.

With such a minimal parameterization overhead, AR coverage considerably improves the illustration energy of PG strategies. We comment that PG with AR coverage (PG-AR) can concurrently symbolize all optimum coverage modes within the permutation recreation.

Figure: the heatmaps of actions for insurance policies discovered by PG-Ind (left) and PG-AR (center), and the heatmap for rewards (proper); whereas PG-Ind solely converge to a particular mode within the 4-player permutation recreation, PG-AR efficiently discovers all of the optimum modes.

In extra complicated environments, together with SMAC and GRF, PG-AR can study attention-grabbing emergent behaviors that require sturdy intra-agent coordination which will by no means be discovered by PG-Ind.

Figure 6: (high) emergent habits induced by PG-AR in SMAC and GRF. On the 2m_vs_1z map of SMAC, the marines hold standing and assault alternately whereas guaranteeing there is just one attacking marine at every timestep; (backside) within the academy_3_vs_1_with_keeper state of affairs of GRF, brokers study a “Tiki-Taka” fashion habits: every participant retains passing the ball to their teammates.

Discussions and Takeaways

In this put up, we offer a concrete evaluation of VD and PG strategies in cooperative MARL. First, we reveal the limitation on the expressiveness of widespread VD strategies, exhibiting that they might not symbolize optimum insurance policies even in a easy permutation recreation. By distinction, we present that PG strategies are provably extra expressive. We empirically confirm the expressiveness benefit of PG on widespread MARL testbeds, together with SMAC, GRF, and Hanabi Challenge. We hope the insights from this work may gain advantage the group in direction of extra common and extra highly effective cooperative MARL algorithms sooner or later.

This put up is predicated on our paper in joint with Zelai Xu: Revisiting Some Common Practices in Cooperative Multi-Agent Reinforcement Learning (paper, web site).