MARL with General Utilities via Decentralized Shadow Reward Actor-Critic
  We posit a new mechanism for cooperation in multi-agent reinforcement
learning (MARL) based upon any nonlinear function of the team's long-term
state-action occupancy measure, i.e., a \emph{general utility}. This subsumes
the cumulative return but also allows one to incorporate risk-sensitivity,
exploration, and priors. % We derive the {\bf D}ecentralized {\bf S}hadow
Reward {\bf A}ctor-{\bf C}ritic (DSAC) in which agents alternate between policy
evaluation (critic), weighted averaging with neighbors (information mixing),
and local gradient updates for their policy parameters (actor). DSAC augments
the classic critic step by requiring agents to (i) estimate their local
occupancy measure in order to (ii) estimate the derivative of the local utility
with respect to their occupancy measure, i.e., the "shadow reward". DSAC
converges to $\epsilon$-stationarity in $\mathcal{O}(1/\epsilon^{2.5})$
(Theorem \ref{theorem:final}) or faster $\mathcal{O}(1/\epsilon^{2})$
(Corollary \ref{corollary:communication}) steps with high probability,
depending on the amount of communications. We further establish the
non-existence of spurious stationary points for this problem, that is, DSAC
finds the globally optimal policy (Corollary \ref{corollary:global}).
Experiments demonstrate the merits of goals beyond the cumulative return in
cooperative MARL.
