# MARL with General Utilities via Decentralized Shadow Reward Actor-Critic

arXiv: https://arxiv.org/abs/2106.00543 · HTML: https://mlsanity.com/paper/2106.00543/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 69 references that are in the map.
- First posted on arXiv 29 May 2021.

## Builds on (most cited first, 28 of 28)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Multi-agent Reinforcement Learning in Sequential Social Dilemmas](https://mlsanity.com/paper/1702.03037/) (2017)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [MAVEN: Multi-Agent Variational Exploration](https://mlsanity.com/paper/1910.07483/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1702.08887/) (2017)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Deep Reinforcement Learning for Page-wise Recommendations](https://mlsanity.com/paper/1805.02343/) (2018)
- [Coordinated Multi-Agent Imitation Learning](https://mlsanity.com/paper/1703.03121/) (2017)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Biases for Emergent Communication in Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1912.05676/) (2019)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [UneVEn: Universal Value Exploration for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2010.02974/) (2020)
- [Variance-Constrained Actor-Critic Algorithms for Discounted and Average Reward MDPs](https://mlsanity.com/paper/1403.6530/) (2014)
- [Active Exploration in Markov Decision Processes](https://mlsanity.com/paper/1902.11199/) (2019)
- [Optimization for Reinforcement Learning: From Single Agent to Cooperative Agents](https://mlsanity.com/paper/1912.00498/) (2019)
- [Value Propagation for Decentralized Networked Deep Multi-agent Reinforcement Learning](https://mlsanity.com/paper/1901.09326/) (2019)
- [Cautious Reinforcement Learning via Distributional Risk in the Dual Domain](https://mlsanity.com/paper/2002.12475/) (2020)
- [Negotiating Team Formation Using Deep Reinforcement Learning](https://mlsanity.com/paper/2010.10380/) (2020)
- [Communication-Efficient Policy Gradient Methods for Distributed Reinforcement Learning](https://mlsanity.com/paper/1812.03239/) (2018)
- [Correcting Experience Replay for Multi-Agent Communication](https://mlsanity.com/paper/2010.01192/) (2020)
- [Decentralized stochastic control](https://mlsanity.com/paper/1310.4545/) (2013)
- [Online Planning for Decentralized Stochastic Control with Partial History Sharing](https://mlsanity.com/paper/1908.02357/) (2019)
- [Optimality Conditions for Inventory Control](https://mlsanity.com/paper/1606.00957/) (2016)

## Built on by (most cited first, 5 of 5)

- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [MDPGT: Momentum-based Decentralized Policy Gradient Tracking](https://mlsanity.com/paper/2112.02813/) (2021)
- [Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communication](https://mlsanity.com/paper/2110.07392/) (2021)
- [Offsetting Unequal Competition through RL-assisted Incentive Schemes](https://mlsanity.com/paper/2201.01450/) (2022)

## Abstract (arXiv)

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 general utility. This subsumes the cumulative return but also allows one to incorporate risk-sensitivity, exploration, and priors. % We derive the bf Decentralized bf Shadow Reward bf Actor-bf Critic (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 ε-stationarity in O(1/ε2.5) (Theorem reftheorem:final) or faster O(1/ε2) (Corollary refcorollary: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 refcorollary:global). Experiments demonstrate the merits of goals beyond the cumulative return in cooperative MARL.