Stable and Efficient Shapley Value-Based Reward Reallocation for Multi-Agent Reinforcement Learning of Autonomous Vehicles

Songyang Han, He Wang, Sanbao Su, Yuanyuan Shi, Fei Miao

Introduction

In the development of Connected Autonomous Vehicles (CAVs), a common assumption is that connectivity naturally leads to cooperation. However, in decentralized systems where individual agents are programmed to maximize personal utility—such as speed or travel time—cooperation is not guaranteed. Standard Multi-Agent Reinforcement Learning (MARL) algorithms often struggle to incentivize agents to perform maneuvers that benefit the collective at a personal cost. This paper addresses the fundamental challenge of reallocating system rewards to ensure that self-interested agents are motivated to cooperate within a stable coalition.

Methodology

The proposed framework bridges MARL with Cooperative Game Theory by introducing a reward reallocation mechanism based on the Shapley value. The approach follows a structured process:

  1. Transferable Utility (TU) Game Formulation: The CAV environment is modeled as a game where the value of any coalition of vehicles can be quantified.
  2. Characteristic Function Definition: A function $v(s, a, C)$ represents the expected discounted total reward a coalition $C$ can achieve given the current state and actions.
  3. Shapley Value Reallocation: Instead of raw local rewards, the system calculates the Shapley value for each agent, assigning a "fair" payout based on their marginal contribution to all possible coalitions.
  4. Stability and the Core: The authors mathematically prove that if the game is "convex" (meaning the incentive to join a group increases with group size), the Shapley value allocation lies in the Core. This ensures no sub-group has an incentive to defect.
  5. Algorithmic Implementation: A modified Actor-Critic algorithm is employed, where a neural network approximates the characteristic function to compute the Shapley values that guide policy updates.

Experimental Setup

The researchers evaluated the framework using the CARLA simulator, focusing on a high-fidelity three-lane freeway scenario.

The CARLA simulation environment featuring a three-lane freeway.

The setup involved a mix of 30 vehicles, including CAVs controlled by the proposed algorithm and human-driven vehicles managed by CARLA's autopilot. Input data consisted of simulated camera images and LIDAR point clouds, processed via ResNet-18 and PointPillars for robust object detection.

Results and Discussion

The Shapley-based method was benchmarked against state-of-the-art algorithms, including MADDPG, M3DDPG, and COMA.

Training performance comparison showing mean episode system rewards.

Key findings include:

  • Superior System Reward: The proposed method achieved a significantly higher mean episode system reward than all baselines, indicating more efficient overall traffic flow.
  • Scalability in Mixed Traffic: The algorithm demonstrated strong performance across varying CAV penetration rates. Transitioning from 0% to 100% CAVs resulted in a 10% increase in average velocity and an 8% improvement in passenger comfort.
  • Stability over COMA: Even at low penetration rates, the Shapley-based reallocation outperformed the Counterfactual Multi-Agent (COMA) algorithm in both speed and comfort metrics.

The success of this approach stems from the fact that fairness, as defined by the Shapley value (symmetry and additivity), stabilizes the learning process. By identifying the convex nature of CAV rewards, the authors provide a mathematical guarantee for stable cooperation.

Limitations and Future Work

While effective, the method exhibits slower initial convergence compared to some baselines, as agents must first learn an accurate estimation of the characteristic function. Additionally, while tested with 30 vehicles, the combinatorial complexity of calculating coalitions may pose challenges in extremely dense urban environments. Future research will explore scaling to massive swarms and applying this framework to other networked Cyber-Physical Systems, such as smart grids or industrial robotics.

Summary updated

Abstract

With the development of sensing and communication technologies in networked cyber-physical systems (CPSs), multi-agent reinforcement learning (MARL)-based methodologies are integrated into the control process of physical systems and demonstrate prominent performance in a wide array of CPS domains, such as connected autonomous vehicles (CAVs). However, it remains challenging to mathematically characterize the improvement of the performance of CAVs with communication and cooperation capability. When each individual autonomous vehicle is originally self-interest, we can not assume that all agents would cooperate naturally during the training process. In this work, we propose to reallocate the system's total reward efficiently to motivate stable cooperation among autonomous vehicles. We formally define and quantify how to reallocate the system's total reward to each agent under the proposed transferable utility game, such that communication-based cooperation among multi-agents increases the system's total reward. We prove that Shapley value-based reward reallocation of MARL locates in the core if the transferable utility game is a convex game. Hence, the cooperation is stable and efficient and the agents should stay in the coalition or the cooperating group. We then propose a cooperative policy learning algorithm with Shapley value reward reallocation. In experiments, compared with several literature algorithms, we show the improvement of the mean episode system reward of CAV systems using our proposed algorithm.
BibTeX
@inproceedings{han2022stable,
  author = {Songyang Han and He Wang and Sanbao Su and Yuanyuan Shi and Fei Miao},
  title = {{Stable and Efficient Shapley Value-Based Reward Reallocation for Multi-Agent Reinforcement Learning of Autonomous Vehicles}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2022},
  url = {https://openreview.net/forum?id=TBrbEj96jj},
}
Figure