PaperlayerView exact revision on arXiv

Source-linked AI summary

Shapley Q-value: A Local Reward Approach to Solve Global Reward Games

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

arXiv:1907.05707v6cs.LGcs.AIcs.MA

TL;DR

Global reward games need credit assignment that reflects individual contributions rather than assigning every agent the same reward. The paper introduces ECG, Shapley Q-value, and SQDDPG, reporting fair credit assignment and faster convergence across three tasks, while noting theoretical and implementation limitations.

  • Problem

    Shared rewards may assign inaccurate individual contributions, leaving credit assignment insufficiently explained by conventional non-cooperative game theory.

  • Method

    The paper introduces extended convex game (ECG), Shapley Q-value for local credit assignment, and SQDDPG with Shapley Q-values as centralized critics for decentralized policies.

  • Results

    SQDDPG shows fair credit assignments and fast convergence across Cooperative Navigation, Prey-and-Predator, and Traffic Junction compared with baseline methods.

  • Takeaways & Limitations

    The results support contribution-based local rewards as a useful approach for credit assignment in global reward games.

  • Takeaways & Limitations

    The theoretical global-optimum guarantee depends on convexity, which cannot be guaranteed in applications, and ECG assumes an initially scheduling oracle that is difficult to implement.

Abstract

from arXiv · show

Cooperative game is a critical research area in the multi-agent reinforcement learning (MARL). Global reward game is a subclass of cooperative games, where all agents aim to maximize the global reward. Credit assignment is an important problem studied in the global reward game. Most of previous works stood by the view of non-cooperative-game theoretical framework with the shared reward approach, i.e., each agent being assigned a shared global reward directly. This, however, may give each agent an inaccurate reward on its contribution to the group, which could cause inefficient learning. To deal with this problem, we i) introduce a cooperative-game theoretical framework called extended convex game (ECG) that is a superset of global reward game, and ii) propose a local reward approach called Shapley Q-value. Shapley Q-value is able to distribute the global reward, reflecting each agent's own contribution in contrast to the shared reward approach. Moreover, we derive an MARL algorithm called Shapley Q-value deep deterministic policy gradient (SQDDPG), using Shapley Q-value as the critic for each agent. We evaluate SQDDPG on Cooperative Navigation, Prey-and-Predator and Traffic Junction, compared with the state-of-the-art algorithms, e.g., MADDPG, COMA, Independent DDPG and Independent A2C. In the experiments, SQDDPG shows a significant improvement on the convergence rate. Finally, we plot Shapley Q-value and validate the property of fair credit assignment.

1 Introduction

The paper frames credit assignment as a central challenge in global reward games and introduces cooperative-game theory to explain contribution-based rewards. It proposes ECG, Shapley Q-value, and SQDDPG as a theoretical and algorithmic solution.

  • Motivation: Global reward games require assigning a shared global reward among agents pursuing the same objective.Credit assignment seeks a method for distributing the global reward.
  • Motivation: Shared reward approaches assign the global reward directly, whereas local reward approaches distribute it according to each agent’s contribution.The paper notes that local reward approaches have superior performance in many tasks.
  • Motivation: Non-cooperative game theory emphasizes individual rewards and Nash equilibrium, providing no explicit cooperation incentive for global reward games.Shared rewards are therefore used to force cooperation under that formulation.
  • Contributions: Extended convex game (ECG) extends convex games to infinite-horizon settings and contains global reward games as a special case.A global reward game corresponds to an ECG with the grand coalition and an efficient payoff distribution scheme.
  • Contributions: Shapley Q-value distributes global rewards according to agents’ contributions, and SQDDPG uses these values as centralized critics for decentralized policies.The algorithm is evaluated on Cooperative Navigation, Prey-and-Predator, and Traffic Junction against several baselines.

2 Related Work

The related work contrasts cooperative objectives and credit-assignment strategies, motivating a cooperative-game formulation that represents global reward games through a grand coalition.

  • Cooperative Game: Cooperative-game agents coordinate on joint tasks or maximize global payoff, unlike agents in competing games.The paper situates MARL as reinforcement learning for cooperative multi-agent games.
  • Cooperative Game: Existing global reward-game frameworks commonly use non-cooperative game theory and shared rewards to align agents’ objectives.Potential functions have been used to make agents share the same global-reward objective.
  • Cooperative Game: The paper interprets a global reward game as a cooperative-game framework in which all agents form the grand coalition.This provides a new theoretical view of global reward games and credit assignment.
  • Credit Assignment: Shared reward assigns every agent the global reward equally, but may fail to represent individual contributions in difficult problems.This limitation motivates local reward methods that quantify agents’ contributions.

3 Preliminaries

The preliminaries define convex-game payoff allocation and Shapley-value fairness, then connect policy-gradient learning to agent-specific Q-value contribution estimates in MARL.

  • Convex Game: A convex game represents agents, coalition values, coalition structures, and local-reward payoffs subject to feasibility constraints.Its core is a stable solution set ensuring a reasonable payoff distribution.
  • Shapley Value: The Shapley value averages each agent’s marginal contribution across all possible coalitions in a grand coalition.For agent i, the marginal contribution is δ_i(C) = v(C ∪ {i}) − v(C).
  • Shapley Value: Shapley-value fairness includes efficiency, the dummy-player property, and symmetry.These properties require total allocated payoff to equal coalition value, zero payoff for noncontributors, and equal payoff for equally contributing agents.
  • Policy Gradient: Policy gradients use Q^π(s, a) to estimate action contributions when optimizing an agent’s policy.The multi-agent formulation expresses each agent’s gradient using its agent-specific Q-value.
  • Policy Gradient: The paper applies the deterministic policy-gradient formulation to learn each agent’s deterministic policy.This connects the policy-gradient preliminaries to the algorithm developed later.

4 Our Work

The paper develops ECG as an infinite-horizon cooperative-game framework for global reward games, then uses Shapley-based local rewards to design SQDDPG and support efficient credit assignment. It also characterizes shared rewards, derives Shapley Q-values, and notes that practical learning may converge only to local optima.

  • 4.1 Extended Convex Game: ECG extends convex games to infinite-horizon settings and shows that global reward games correspond to ECGs with the grand coalition.With an efficient payoff distribution scheme, the grand coalition can achieve maximal social welfare.
  • 4.4 Shapley Q-value Deep Deterministic Policy Gradient: SQDDPG uses Shapley Q-values as centralized critics while retaining decentralized policies during execution.Its objective uses the global reward to preserve efficient payoff distribution across agents.
  • 4.1 Extended Convex Game: Shapley value lies in the core of an ECG with the grand coalition, making it a theoretically suitable local reward distribution scheme.The theorem connects core membership and efficient payoff distribution to the global objective.
  • 4.2 Looking into the Shared Reward Approach by the View of ECG: The shared reward approach assigns each agent vπ({N})/|N|, satisfying efficiency but not guaranteeing the optimal solution.The paper contrasts this equal allocation with Shapley value, which theoretically guarantees convergence to the maximal global value under the stated ECG properties.
  • 4.3 Shapley Q-value: Shapley Q-value models coalition rewards as Q-values and estimates each agent’s marginal contribution for local credit assignment.Approximate marginal contribution avoids learning two Q-value functions for every coalition and agent combination.
  • 4.4 Shapley Q-value Deep Deterministic Policy Gradient: The global maximum guaranteed by ECG theory may not be achieved in applications because the algorithm can converge to a local optimum.The paper states that convexity of the global value cannot generally be guaranteed in applications.

5 Experiments

Experiments evaluate SQDDPG across Cooperative Navigation, Prey-and-Predator, and Traffic Junction against independent and centralized-critic baselines. SQDDPG shows faster convergence, reaches prey-capture performance in about 25 turns, and achieves strong Traffic Junction success rates while producing interpretable credit assignments.

  • Cooperative Navigation: SQDDPG and its sample-size variants outperform baselines on convergence rate in Cooperative Navigation.SQDDPG with sample size 1 is used in later experiments to reduce computational complexity.
  • Prey-and-Predator: Around 25 turns are needed for SQDDPG to capture the prey finally, with MADDPG and IDDPG following.
  • Credit assignment: SQDDPG assigns credit inversely to predators’ distance from the prey, with PCC 0.3210 and two-tailed p-value 1.9542e-19.The correlation is calculated from 1000 randomly selected transition samples.
  • Traffic Junction: SQDDPG achieves success rates of 88.98% on medium and 87.04% on hard Traffic Junction, outperforming the baselines.On the easy version, all algorithms except IA2C exceed 93%.
  • Traffic Junction: SQDDPG significantly exceeds reported no-communication success rates of 84.9% and 74.1% on Traffic Junction.
  • Discussion: The discussion reports that SQDDPG’s local-reward credit assignment is more significant on fairness than COMA’s.

6 Conclusion

The conclusion presents ECG as a broader cooperative-game framework and SQDDPG as its Shapley-Q-value-based algorithm. Across three global reward games, SQDDPG shows promising performance, fair credit assignment, and fast convergence.

  • The paper extends global reward games to the broader extended convex game framework.
  • SQDDPG uses Shapley Q-value as a local-reward approach and is theoretically guaranteed to find the optimal solution in an ECG with the grand coalition.
  • Across Cooperative Navigation, Prey-and-Predator, and Traffic Junction, SQDDPG shows promising performance, fair credit assignments, and fast convergence.

Algorithm

This section presents the pseudocode for the SQDDPG algorithm in Algorithm 1.

  • Algorithm 1 provides the pseudocode for Shapley Q-value deep deterministic policy gradient (SQDDPG).

Proof of Theorem 1

Theorem 1 establishes that an extended convex game with an efficient payoff distribution scheme has a core solution using the grand coalition, whose objective maximizes global reward and social welfare.

  • The resulting objective is maxπ vπ({N}), which maximizes the global reward and achieves at least the value of every alternative coalition structure.
  • The proof defines each coalition’s optimal value as the maximum cumulative reward achievable under its joint policy.For a coalition structure, the optimal value is the sum of the optimal values of its constituent coalitions.
  • The proof first shows that an efficient payoff distribution scheme exists for the grand coalition and yields at least as much value as any other coalition structure.
  • The grand coalition’s payoff distribution is shown to satisfy the core conditions, contradicting the assumption that it is not a core solution.

Experimental Setups

The experiments use SQDDPG with centralized Shapley Q-value critics and compare it with independent and centralized-critic MARL algorithms under matched network and training settings.

  • All algorithms use one-hidden-layer MLP policy and critic networks, with matched learning rates, regularization, update frequency, batch size, and hidden-unit counts.Training uses Adam with default hyperparameters except for the learning rate.
  • SQDDPG initializes actor and critic parameters, target networks, coalition-sampling size M, target-update rate τ, discount rate γ, and replay training settings.
  • For each agent, SQDDPG samples ordered coalitions, masks irrelevant actions, and constructs coalition-specific inputs for Shapley Q-value estimation.
  • The algorithm updates each actor with deterministic policy gradients and each critic by minimizing its specified optimization objective.
  • Centralized-critic methods share states during training, whereas decentralized-critic methods observe only each agent’s own state.

Additional Details of Cooperative Navigation

The Cooperative Navigation experiments specify algorithm-specific hyperparameters in Table 3.

  • Table 3 lists the hyperparameters used by each algorithm in Cooperative Navigation.

Additional Details of Prey-and-Predator

The additional experiments describe task settings, hyperparameters, and visual analyses for Prey-and-Predator and Traffic Junction, including credit assignments and training curves.

  • Prey-and-Predator: Table 4 provides the Prey-and-Predator hyperparameters, while Figure 5 visualizes normalized credit assignments for predators along an expert-policy trajectory.
  • Traffic Junction: Traffic Junction settings vary by difficulty, including car-arrival probability, car count, entry-point count, and route count.
  • Traffic Junction: Figures 6a–6c show mean rewards and Figures 6d–6f show success rates during Traffic Junction training, while Figure 7 illustrates entry points, routes, and two-way roads.
  • Motivation: The shared-reward framework lacks clear credit-assignment explanations, may slow learning when credits are equal, and is difficult to extend to coalition-based problems.
  • Limitations: The ECG framework assumes an oracle initially schedules coalitions, but this oracle is difficult to implement and cannot handle some random perturbations.
Loading 1907.05707v6…