MARL, Part 4: Multi-Agent Policy Gradients

Part 2 examined credit assignment and value factorization; Part 3 established when a centralized critic preserves a local actor's gradient. We now use those results to study the update itself. We derive the team gradient, identify how replay changes it, and account for teammates whose policies have already been updated.

Recap: Differentiating a product policy

With separate agent parameters and independent action draws conditional on joint history $h$, the earlier factorization gives

Here $h_j$ is agent $j$'s local history. Only its own policy factor depends on $\theta_i$. This identity supplies each partial gradient below; shared parameters require a sum over the affected factors instead.

1. Differentiate the joint policy

Use Part 3's finite-horizon cooperative model. There are $N$ agents, $T$ decisions, bounded shared rewards, and $0\le\gamma\le1$. Agent $i$ observes its local history $H_{i,t}$, a projection of the joint history $H_t$. Conditional on $H_t=h$, independent private action draws give

Action, observation, state, and reward spaces are finite here. Assume positive, continuously differentiable action probabilities and separate parameter vectors $\theta_i$. The initial distribution and environment kernels do not depend on $\theta$. Writing their product as $p_{\rm env}(\tau)$, the full trajectory law is

This defines $P_\theta$. Histories, actions, and rewards in every on-policy expectation below are sampled from this law. Parameters remain fixed while an episode is generated. For recurrent actors, score derivatives include the dependence through their unrolled memory updates. Set

Define exact conditional values on histories of positive probability:

The multi-agent score identity

First, differentiate the finite trajectory sum. The likelihood-ratio identity and product policy give

Next, condition on $H_t$. Normalization of the local action distribution implies

Rewards before time $t$ are measurable with respect to $H_t$, so their score-weighted expectations vanish. Since $G_0=\sum_{k<t}\gamma^kR_{k+1}+\gamma^tG_t$, conditioning on $(H_t,\boldsymbol A_t)$ then yields

The last equality uses the same zero-score identity to subtract $V_t^\theta(H_t)$. This is an exact derivative, not a claim that a fitted critic is exact. A physical-state-only critic needs the additional sufficiency conditions discussed in Part 3.

COMA instead subtracts an agent-specific counterfactual baseline. Its cancellation uses $\mathbb E[\psi_{i,t}\mid H_t,\boldsymbol A_{-i,t}]=0$: the other agents' actions do not reveal agent $i$'s private action draw once $H_t$ is fixed. The choice changes the estimator, not the team objective.

Shared parameters change the derivative

If every policy uses the same parameter vector $\vartheta$, every action factor contributes:

Adding the agents' score contributions is therefore necessary. Averaging them instead rescales the gradient by $1/N$; treating all but one shared-parameter actor as fixed changes the derivative. Sharing weights still does not share observations at deployment.

2. Deterministic actors and MADDPG

We now change the model: the trainer observes a finite Markov state, joint actions are continuous, and actors are stationary deterministic maps of fixed local features:

Each $o_i(s)$ is a fixed local feature map. There is no unrecorded actor memory in this specialization. Let $0\le\gamma<1$, initial law $S_0\sim\rho_0$, mean reward $r(s,\boldsymbol a)$, and transitions $S'\mid s,\boldsymbol a\sim P(\cdot\mid s,\boldsymbol a)$. Assume bounded rewards and continuous derivatives of $r,P,\mu_i$ on a neighborhood of the actions used. Parameters are separate.

Click to enlarge · Scroll sideways on small screens

The deterministic value satisfies

Write $z_i(s)=\nabla_{\theta_i}V^\mu(s)$. Differentiating the Bellman equation gives

Here $D_{\theta_i}\mu_i$ is an action-by-parameter Jacobian; $\nabla_{a_i}Q^\mu$ holds the continuation policy fixed. It already includes the derivative of the immediate reward and transition probabilities. The remaining $z_i$ term differentiates future values.

Because $P^\mu$ is stochastic and $\gamma<1$, the Neumann series converges:

Define the normalized discounted state occupancy

Multiplying the series by $\rho_0^\top$ establishes

This is the multi-agent deterministic gradient under the stated model, obtained by the same Bellman differentiation as Silver et al., Theorem 1. All agents' actions inside the exact critic are their current actions.

Replay changes both the state law and teammates' actions

Multi-agent deep deterministic policy gradient (MADDPG) uses replay and fitted centralized critics. Following Lowe et al., Section 4.1, let $(S,\boldsymbol A,R,S')\sim\nu_{\mathcal D}$ denote a transition drawn from a fixed replay buffer. A team-critic version uses

Target parameters $w^-,\mu^-$ are frozen during this regression; terminal transitions use zero continuation. The paper also allows different rewards and critics for different agents. Its replay-based actor update, specialized to a team reward, has direction

Relative to the exact gradient, this direction uses a fitted critic in place of $Q^\mu$, replay states in place of $d_\mu$, and recorded teammate actions in place of their current actions. A learning-rate rescaling cannot correct these changes. Silver et al., Equation 15 likewise treats its off-policy direction as an approximation.

For example, consider one decision with $r(a_1,a_2)=-(a_1+a_2-1)^2$. At current actions $(0.2,0.2)$,

The recorded teammate action therefore reverses this derivative even with an exact critic. The discrepancy comes from which joint action is evaluated, not from critic estimation.

To isolate the state-law issue, let $d_{\mathcal D}$ be replay's state marginal, with $d_{\mathcal D}(s)>0$ wherever $d_\mu(s)>0$. An exact change of measure gives

This identity still requires the exact $b_i$ evaluated at the agents' current actions. It does not tell us the required state-visitation ratio. Nor does it resolve missing action coverage or make an ordinary replay update an exact on-policy gradient.

3. Local clipping is not joint policy control

Return to the finite-horizon stochastic model in Section 1. Freeze an old product policy $\pi$ and consider a candidate $\bar\pi$, both positive. Choose $0<\varepsilon<1$. At fixed $(t,h,\boldsymbol a)$ define

For any function $f$ of the joint action, the conditional change of measure is

Even if every actual local ratio were restricted to $[1-\varepsilon,1+\varepsilon]$, the joint ratio would only satisfy

With ten agents and $\varepsilon=0.2$, this interval is approximately $[0.107,6.192]$. These extremes are attainable at particular joint actions: ten Bernoulli policies changing from probability $0.5$ to $0.6$ give ratios $1.2^{10}$ at all ones and $0.8^{10}$ at all zeros.

At a fixed history, KL divergence also accumulates across agents. Expanding the logarithm and summing out the other actions gives

PPO clipping is weaker than imposing either displayed restriction: it clips a branch of an objective, not the policy probabilities themselves.

MAPPO's local clipped objective

Let $\widehat A_t$ be a frozen team-advantage estimate from an old-policy batch. A per-agent PPO objective is

At $\bar\pi_i=\pi_i$, with an exact advantage and separate parameters, its derivative equals agent $i$'s team gradient. For a finite change, it changes only one action factor while retaining the old trajectory law. Concurrently maximizing these local objectives does not make them an exact joint objective for the updated team.

Click to enlarge · Scroll sideways on small screens

With $\widehat A_t>0$, the clipped term is flat once $r_{i,t}>1+\varepsilon$. A flat objective branch supplies no hard constraint preventing a larger ratio, particularly when parameters affect many samples.

Multi-agent PPO (MAPPO) combines PPO-style local actors with centralized value inputs. Its homogeneous-agent implementations often share parameters and sum agents' clipped terms. Parameter sharing is an implementation choice, not the definition of CTDE or a requirement of every multi-agent PPO method.

One common advantage estimate is generalized advantage estimation. For a frozen history-value predictor $\widehat V_t$, with $\widehat V_T=0$ and $0\le\lambda\le1$,

All terms are evaluated on $\tau\sim P_\pi$, with the fitted predictor held fixed. The earlier GAE derivation explains the bias–variance tradeoff. A state-only predictor in a partially observed problem needs the qualifications from Part 3; the formula alone does not establish an unbiased history advantage.

Click to enlarge · Scroll sideways on small screens

These are the authors' SMAC ablations, not results produced here. The same $\varepsilon$ controls both policy and value clipping, so the curves do not isolate the effect of policy clipping. They illustrate practical sensitivity, not a universal optimal $\varepsilon$ or an improvement theorem.

4. Derive the performance-difference identity

To compare two complete policy updates, we need their difference in expected return rather than only a local derivative. Write $V_t^\pi,Q_t^\pi,A_t^\pi$ for the old policy's history values and set $V_T^\pi=0$. Once $(H_t,\boldsymbol A_t)$ is fixed, the environment's next-step law is the same under both policies. Consequently,

Multiply by $\gamma^t$ and sum. Adjacent value terms cancel, the terminal term is zero, and the initial history law is unchanged:

This is an exact finite-horizon identity. The expectation uses candidate-policy histories, not old-policy histories. Since policy probabilities are positive and the environment law is common, the prefix likelihood ratio

changes the old law of $(H_t,\boldsymbol A_t)$ to the new law. Therefore an equivalent expression is

Using only $r_t$ changes the current action distribution but still averages over histories from the old policy. This surrogate has the correct first derivative at $\bar\pi=\pi$. At that point, derivatives of the earlier ratios multiply an old-policy conditional advantage with mean zero, so those terms vanish. For a finite update, however, the surrogate need not equal the true change in performance. Trust-region methods therefore need an argument controlling policy change, not just the likelihood-ratio identity.

5. Account for earlier agents' updates

Fix a time $t$, history $h$, and ordering $i_1,\ldots,i_N$. Suppress $t,h$ temporarily. For an action prefix $\boldsymbol a_{i_{1:m}}$, average over the remaining old-policy actions:

The endpoints are $Q^{\pi,i_{1:0}}=V^\pi$ and $Q^{\pi,i_{1:N}}=Q^\pi$. Define an ordered incremental advantage

The letter $B_m$ distinguishes this quantity from the joint advantage $A^\pi$. The differences telescope:

Moreover, averaging $B_m$ over its last action under the old policy gives zero at every fixed prefix:

These are the telescoping and marginalization identities behind Kuba et al., Lemma 1. They do not assume additive utilities as in VDN or monotonic mixing as in QMIX. The history-based, finite-horizon version here applies the same algebra separately at each $(t,h)$.

Rewrite the incremental improvement using one joint critic

Suppose agents $i_1,\ldots,i_{m-1}$ have already selected new policies. Freeze those policies while updating $i_m$. Define

and the conditional expected increment

First, integrate the unupdated suffix under its old policy. Changing measure for the prefix then gives

The shorthand expectations on the right use exactly the prefix laws in the definition of $\Delta_m$, with $h$ fixed. Subtract the equations. The constant $V^\pi(h)$ also cancels because $\mathbb E_{\pi}[M_m(r_{i_m}-1)\mid h]=0$. Hence

This is the importance-weight identity in Kuba et al., Proposition 2, with histories replacing states. It uses one joint advantage; separate fitted prefix critics are unnecessary. Dropping $M_m$ would evaluate the current agent against old teammates rather than those already updated.

A sufficient improvement condition

Averaging the telescoping decomposition under the complete candidate policy gives

Therefore, if $\Delta_{m,t}(h)\ge0$ for every $m,t$ and every candidate-reachable history, the performance-difference identity proves $J(\bar\pi)\ge J(\pi)$. This is a pointwise sufficient condition. Improving an empirical average over old histories does not establish it.

Click to enlarge · Scroll sideways on small screens

The source's one-state example shows why update order matters. Sample $A_i\sim\mathcal N(\mu_i,1)$ independently for $i=1,2$, with means fixed during sampling. Then $\mathbb E[A_1A_2]=\mu_1\mu_2$.

Start from $(-0.25,0.25)$ and allow each mean to change by at most one. If both agents optimize against the other's old mean, they choose $(0.75,-0.75)$ and reduce return from $-0.0625$ to $-0.5625$. If the first mean changes to $0.75$ before the second agent optimizes, the new pair is $(0.75,1.25)$ and return is $0.9375$. For unit-variance Gaussians, a unit mean displacement has KL divergence $1/2$, as in the plotted trust regions. This one-decision Gaussian example is separate from our finite-action theorem assumptions.

6. HAPPO-style sequential clipped updates

Heterogeneous-agent proximal policy optimization (HAPPO) uses the sequential correction without requiring shared actor parameters. Replace the exact advantage with a frozen estimate and use the old trajectory batch. The actor at position $m$ maximizes

Earlier actors' ratios are fixed during this maximization. Since $M_{m,t}>0$, multiplying outside the minimum is equivalent to multiplying both branches inside it. The constant $-M_{m,t}\widehat A_t$ from the incremental-improvement identity has zero derivative with respect to the current actor, so it can be omitted. This is the sequential clipped construction of HAPPO, Section 4.2.

Input: Old local actors $\pi$; an on-policy batch $\mathcal D\sim P_\pi^{\otimes n}$; frozen estimates $\widehat A_t$; clipping width $0<\varepsilon<1$; an ordering $i_1,\ldots,i_N$ independent of the batch.

Output: Updated local actors $\bar\pi_1,\ldots,\bar\pi_N$.

1. Store old action log probabilities for every agent and decision in $\mathcal D$.
2. Initialize $\bar\pi_i\gets\pi_i$ for all agents.
3. for $m=1,\ldots,N$ do
4. Compute and freeze $M_{m,t}\gets\prod_{j<m}\bar\pi_{i_j,t}(A_{i_j,t}\mid H_{i_j,t})/\pi_{i_j,t}(A_{i_j,t}\mid H_{i_j,t})$ on the batch.
5. for each optimizer iteration for actor $i_m$ do
6. Compute $r_{i_m,t}$ relative to its stored old action probabilities.
7. Ascend the empirical $L_m^{\rm seq}$, averaging the displayed weighted sum over the $n$ episodes; hold all other actors and $\widehat A_t$ fixed.
8. end for
9. Freeze the resulting $\bar\pi_{i_m}$ before proceeding to the next agent.
10. end for
11. Deploy each updated actor using only its own available history.

This is a simplified actor-update pass, not the paper's complete training procedure. Critic fitting, normalization, learning-rate schedules, and fresh data collection require separate choices. Once the batch and fitted advantages are fixed, the displayed objective is a criterion to optimize on those data. It is not an unbiased estimate of the true improvement after a finite update. Sequential parameter updates also do not require agents to act sequentially at deployment.

Kuba et al.'s Theorem 2 proves monotonic improvement for their ideal policy-iteration algorithm with exact advantages, exact optimization, and a prescribed worst-state KL penalty under their assumptions. Practical HAPPO uses a clipped approximation. Neither that theorem nor the pointwise argument above automatically guarantees improvement for this finite-sample pseudocode.

7. What gradient ascent does and does not guarantee

For separate actors sharing $J$, concatenating their exact partial gradients gives $g=\nabla_\theta J$. For a step length $\eta\ge0$, suppose $\nabla J$ is $L$-Lipschitz along the update segment. The fundamental theorem of calculus gives

Thus a sufficiently small exact joint-gradient update is an ascent step. This statement assumes a common objective, exact gradients, and a suitable step size. It does not prove global optimality, improvement for arbitrary independent surrogate maximizers, or improvement for replay-based approximate gradients.

Different rewards change the problem further. In the one-decision zero-sum game $J_1(x,y)=xy$, $J_2(x,y)=-xy$, with $x,y\in[-1,1]$, simultaneous gradient flow in the interior is

For any initial radius in $(0,1)$, the parameters cycle inside the action box instead of approaching the Nash equilibrium $(0,0)$. There is no shared ascent objective here. A policy-gradient formula alone is not a convergence theorem for a game.

The four MARL notes now connect the game model to the learning procedure: Part 2 assigns credit, Part 3 checks the critic's information, and this note identifies the objective and sampling distribution behind each actor update.

References

• Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M. (2014). Deterministic Policy Gradient Algorithms. ICML. Theorem 1 gives the deterministic gradient; Equation 15 identifies an approximate off-policy update.
• Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mordatch, I. (2017). Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. NeurIPS. Section 4.1 gives the centralized deterministic critics and replay-based actor updates; Figure 1 is reproduced above.
• Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S. (2018). Counterfactual Multi-Agent Policy Gradients. AAAI. The counterfactual baseline is derived in Part 2 of this series.
• Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal Policy Optimization Algorithms. Section 3 and Figure 1 explain the clipped surrogate.
• Yu, C., Velu, A., Vinitsky, E., Gao, J., Wang, Y., Bayen, A., and Wu, Y. (2022). The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games. NeurIPS, Datasets and Benchmarks. Sections 3 and 5 describe MAPPO and its implementation study; Figure 7 reports the clipping ablation.
• Kuba, J. G., Chen, R., Wen, M., Wen, Y., Sun, F., Wang, J., and Yang, Y. (2022). Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning. ICLR. Lemma 1, Proposition 2, and Section 4.2 motivate the sequential derivation; Theorem 2 concerns the ideal KL-penalized algorithm, not an unconditional guarantee for clipped HAPPO.

The finite-horizon history derivations, replay-action numerical example, and gradient-flow calculation are worked explanations for this note, not new experimental results. Source figures retain their original plots and attribution.