Shapley Machine: A Game-Theoretic Framework for N-Agent Ad Hoc Teamwork

• URL: http://arxiv.org/abs/2506.11285v1
• Date: Thu, 12 Jun 2025 20:44:09 GMT
• Title: Shapley Machine: A Game-Theoretic Framework for N-Agent Ad Hoc Teamwork
• Authors: Jianhong Wang, Yang Li, Samuel Kaski, Jonathan Lawry,
• Abstract summary: We aim to investigate a recently proposed problem for open multi-agent systems, referred as n-agent ad hoc teamwork (NAHT)<n>Existing methods tend to be based on design and consequently lack theoretical rigor and ambiguous credit assignment among agents.<n>To address these limitations, we model and solve NAHT through the lens of cooperative game theory.
• Score: 25.31548780542065
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Open multi-agent systems are increasingly important in modeling real-world applications, such as smart grids, swarm robotics, etc. In this paper, we aim to investigate a recently proposed problem for open multi-agent systems, referred to as n-agent ad hoc teamwork (NAHT), where only a number of agents are controlled. Existing methods tend to be based on heuristic design and consequently lack theoretical rigor and ambiguous credit assignment among agents. To address these limitations, we model and solve NAHT through the lens of cooperative game theory. More specifically, we first model an open multi-agent system, characterized by its value, as an instance situated in a space of cooperative games, generated by a set of basis games. We then extend this space, along with the state space, to accommodate dynamic scenarios, thereby characterizing NAHT. Exploiting the justifiable assumption that basis game values correspond to a sequence of n-step returns with different horizons, we represent the state values for NAHT in a form similar to $\lambda$-returns. Furthermore, we derive Shapley values to allocate state values to the controlled agents, as credits for their contributions to the ad hoc team. Different from the conventional approach to shaping Shapley values in an explicit form, we shape Shapley values by fulfilling the three axioms uniquely describing them, well defined on the extended game space describing NAHT. To estimate Shapley values in dynamic scenarios, we propose a TD($\lambda$)-like algorithm. The resulting reinforcement learning (RL) algorithm is referred to as Shapley Machine. To our best knowledge, this is the first time that the concepts from cooperative game theory are directly related to RL concepts. In experiments, we demonstrate the effectiveness of Shapley Machine and verify reasonableness of our theory.

Related papers

• Improving LLM General Preference Alignment via Optimistic Online Mirror Descent [57.622821649679786]
  Reinforcement learning from human feedback (RLHF) has demonstrated remarkable effectiveness in aligning large language models (LLMs) with human preferences.<n>In this paper, we drop the Bradley-Terry (BT) model assumption and study LLM alignment under general preferences, formulated as a two-player game.<n>We show that our approach achieves an $O(T-1)$ bound on the duality gap, improving upon the previous $O(T-1/2)$ result.
  arXiv  Detail & Related papers  (2025-02-24T05:24:52Z)
• Principal-Agent Reinforcement Learning: Orchestrating AI Agents with Contracts [20.8288955218712]
  We propose a framework where a principal guides an agent in a Markov Decision Process (MDP) using a series of contracts. We present and analyze a meta-algorithm that iteratively optimize the policies of the principal and agent. We then scale our algorithm with deep Q-learning and analyze its convergence in the presence of approximation error.
  arXiv  Detail & Related papers  (2024-07-25T14:28:58Z)
• Linear Convergence of Independent Natural Policy Gradient in Games with Entropy Regularization [12.612009339150504]
  This work focuses on the entropy-regularized independent natural policy gradient (NPG) algorithm in multi-agent reinforcement learning. We show that, under sufficient entropy regularization, the dynamics of this system converge at a linear rate to the quantal response equilibrium (QRE)
  arXiv  Detail & Related papers  (2024-05-04T22:48:53Z)
• Shapley Value Based Multi-Agent Reinforcement Learning: Theory, Method and Its Application to Energy Network [7.50196317304035]
  This thesis investigates the foundation of credit assignment in multi-agent reinforcement learning via cooperative game theory. We first extend a game model called convex game and a payoff distribution scheme called Shapley value in cooperative game theory. Based on Markov Shapley value, we propose three multi-agent reinforcement learning algorithms called SHAQ, SQDDPG and SPO.
  arXiv  Detail & Related papers  (2024-02-23T13:43:15Z)
• H-SAUR: Hypothesize, Simulate, Act, Update, and Repeat for Understanding Object Articulations from Interactions [62.510951695174604]
  "Hypothesize, Simulate, Act, Update, and Repeat" (H-SAUR) is a probabilistic generative framework that generates hypotheses about how objects articulate given input observations. We show that the proposed model significantly outperforms the current state-of-the-art articulated object manipulation framework. We further improve the test-time efficiency of H-SAUR by integrating a learned prior from learning-based vision models.
  arXiv  Detail & Related papers  (2022-10-22T18:39:33Z)
• On the Convergence of the Shapley Value in Parametric Bayesian Learning Games [28.212413634171572]
  We show that for any two players, their difference in Shapley value converges in probability to the difference in Shapley value of a limiting game whose characteristic function is proportional to the log-determinant of the joint Fisher information. Our result enables this to be achieved without any costly computations of posterior-prior KL divergences.
  arXiv  Detail & Related papers  (2022-05-16T02:29:14Z)
• Collective eXplainable AI: Explaining Cooperative Strategies and Agent Contribution in Multiagent Reinforcement Learning with Shapley Values [68.8204255655161]
  This study proposes a novel approach to explain cooperative strategies in multiagent RL using Shapley values. Results could have implications for non-discriminatory decision making, ethical and responsible AI-derived decisions or policy making under fairness constraints.
  arXiv  Detail & Related papers  (2021-10-04T10:28:57Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Munchausen Reinforcement Learning [50.396037940989146]
  bootstrapping is a core mechanism in Reinforcement Learning (RL) We show that slightly modifying Deep Q-Network (DQN) in that way provides an agent that is competitive with distributional methods on Atari games. We provide strong theoretical insights on what happens under the hood -- implicit Kullback-Leibler regularization and increase of the action-gap.
  arXiv  Detail & Related papers  (2020-07-28T18:30:23Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)
• Distributed Reinforcement Learning for Cooperative Multi-Robot Object Manipulation [53.262360083572005]
  We consider solving a cooperative multi-robot object manipulation task using reinforcement learning (RL) We propose two distributed multi-agent RL approaches: distributed approximate RL (DA-RL) and game-theoretic RL (GT-RL) Although we focus on a small system of two agents in this paper, both DA-RL and GT-RL apply to general multi-agent systems, and are expected to scale well to large systems.
  arXiv  Detail & Related papers  (2020-03-21T00:43:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.