SHAQ: Incorporating Shapley Value Theory into Q-Learning for Multi-Agent Reinforcement Learning

Jianhong Wang, Jinxin Wang, Yuan Zhang, Yunjie Gu, Tae-Kyun Kim

TL;DR

This paper introduces SHAQ, a novel multi-agent reinforcement learning (MARL) algorithm that leverages Shapley Value Theory to provide interpretable value factorization. SHAQ offers superior performance and a deeper understanding of agent contributions in cooperative MARL tasks.

What Problem Does This Paper Address?

In cooperative multi-agent reinforcement learning (MARL), where multiple agents share a global reward, a key challenge is understanding how to attribute that reward to individual agents. Value factorization techniques aim to decompose the global value into individual agent contributions, but their underlying mechanisms and interpretability have been limited. Existing methods often struggle to provide clear insights into why certain agents receive more credit than others, especially in complex scenarios. This lack of interpretability hinders debugging, trust, and the development of more sophisticated MARL systems. The paper addresses this by proposing a theoretically grounded framework that connects cooperative game theory (specifically Shapley values) with MARL value factorization.

Methods

The core of this work is the introduction of Markov Shapley Value (MSV), a generalization of Shapley values to dynamic, Markovian environments. MSV is derived from a new concept called Markov Convex Game (MCG). Based on the properties of MSV, the authors derive the Shapley-Bellman Optimality Equation (SBOE), which provides a theoretical basis for optimal value factorization. To solve SBOE, they propose the Shapley-Bellman Operator (SBO). Finally, a practical MARL algorithm, Shapley Q-Learning (SHAQ), is developed as a stochastic approximation of SBO. SHAQ aims to learn the optimal MSV, which in turn guides the value factorization and credit assignment process. The algorithm is designed to be compatible with the centralized training, decentralized execution (CTDE) paradigm.

Datasets

The paper evaluates SHAQ on two benchmark environments:

  • Predator-Prey: A partially-observable cooperative task where predators aim to capture preys.
  • StarCraft Multi-Agent Challenge (SMAC): A suite of challenging micromanagement tasks from the StarCraft II game, featuring partial observability and complex dynamics.

Key Insights and Ideas

  • Shapley Values for MARL Interpretability: The paper demonstrates that Shapley Value Theory, a well-established concept in cooperative game theory, can be effectively adapted to MARL to provide a theoretically sound and interpretable framework for value factorization.
  • Markov Shapley Value (MSV): Generalizing Shapley values to dynamic environments is crucial for understanding agent contributions in sequential decision-making tasks. MSV provides a principled way to do this.
  • SBOE and SBO: The derivation of the Shapley-Bellman Optimality Equation and Operator provides a theoretical foundation for learning optimal value factorizations, bridging the gap between game theory and reinforcement learning.
  • SHAQ: Interpretable Value Factorization: SHAQ not only achieves competitive or superior performance but also offers a transparent view of how credit is assigned to agents, aligning with theoretical predictions. This interpretability is a significant advantage over many existing black-box MARL methods.
  • Connection to Markov Core: The work establishes that solving SBOE is equivalent to solving the Markov core for cooperative games, implying that SHAQ leads to policies where no agent has an incentive to deviate from the grand coalition.

Key Results

  • Superior Performance: SHAQ demonstrates superior or competitive performance across various tasks in Predator-Prey and the SMAC benchmark compared to state-of-the-art baselines like COMA, VDN, QMIX, and QTRAN. For instance, in Predator-Prey, SHAQ consistently solves tasks across different coordination levels (varying 'p' values). In SMAC, SHAQ outperforms most baselines on several maps, including hard and super-hard scenarios.
  • Interpretability: The paper provides visualizations and analyses showing that SHAQ's credit assignments align with agent behavior and theoretical predictions. For example, in Predator-Prey, agents that actively participate in capturing prey receive higher credits, while "dummy" agents receive near-zero credits, consistent with MSV properties.
  • Theoretical Guarantees: The paper provides theoretical proofs for the convergence of SHAQ to optimal policies and its connection to the Markov core.

Limitations and Future Work

  • Focus on Grand Coalition: The current framework and SHAQ algorithm primarily focus on scenarios with a grand coalition (all agents cooperating). The authors suggest extending the framework to study more general coalition games where different coalition structures may compete or cooperate.
  • Learning Complexity: While SHAQ converges to the Markov core, the learning process can be complicated, especially when dynamically forming coalition structures.
  • Robustness and Reliability: The paper acknowledges that the current theory does not explicitly consider robustness, and the use of neural networks for implementation might raise reliability concerns. Future work could explore robustness as an extension and investigate alternative implementations.
  • Dynamic Coalition Formation: Investigating dynamically forming coalition structures and conducting credit assignments simultaneously is identified as a promising future research direction.

Summary updated

Abstract

Value factorisation is a useful technique for multi-agent reinforcement learning (MARL) in global reward game, however its underlying mechanism is not yet fully understood. This paper studies a theoretical framework for value factorisation with interpretability via Shapley value theory. We generalise Shapley value to Markov convex game called Markov Shapley value (MSV) and apply it as a value factorisation method in global reward game, which is obtained by the equivalence between the two games. Based on the properties of MSV, we derive Shapley-Bellman optimality equation (SBOE) to evaluate the optimal MSV, which corresponds to an optimal joint deterministic policy. Furthermore, we propose Shapley-Bellman operator (SBO) that is proved to solve SBOE. With a stochastic approximation and some transformations, a new MARL algorithm called Shapley Q-learning (SHAQ) is established, the implementation of which is guided by the theoretical results of SBO and MSV. We also discuss the relationship between SHAQ and relevant value factorisation methods. In the experiments, SHAQ exhibits not only superior performances on all tasks but also the interpretability that agrees with the theoretical analysis. The implementation of this paper is on https://github.com/hsvgbkhgbv/shapley-q-learning.
BibTeX
@inproceedings{wang2022shaq,
  author = {Jianhong Wang and Jinxin Wang and Yuan Zhang and Yunjie Gu and Tae-Kyun Kim},
  title = {{SHAQ: Incorporating Shapley Value Theory into Q-Learning for Multi-Agent Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=BjGawodFnOy},
}
Figure