Research map / Multi-agent systems and games / Cooperative multi-agent RL
Detecting Influence Structures in Multi-Agent Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces total and state influence measurement functions and the impact-based TIM/SIM quantities for multi-agent average-reward MDPs, with decentralized stochastic-approximation estimators that have convergence guarantees and are validated in a random MDP and a multi-agent coin game.
Problem
Quantifying how much influence one agent can exert on another's expected return in multi-agent reinforcement learning, especially in the average reward setting where existing measures are largely limited to discounted rewards and lack convergence guarantees.
Approach
Define an impact sample as the max-minus-min effect one agent's action has on another agent's individual state-action function, average it over the stationary distribution to get total impact measurement (TIM) and per-state state impact measurement (SIM), and estimate them with decentralized stochastic approximation that only needs observed actions.
Key results
- In the random 5-agent MDP, TIM and SIM approximation errors decrease monotonically over time across 50 seeds, including under a learning policy.
- In the coin game, TIM estimates recover the asymmetric penalty structure: agent 1 has high impact on agents 2 and 3, while agent 2 has minimal effect on agent 1.
- Theorems give convergence of the TIM and SIM estimators almost surely and an error bound of 2 times the Q-function approximation error in sup norm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of additional agent dependencies | TIM and SIM approximation algorithms · Random environment, static policy | approximation error | Mixed |
| Use a changing policy instead of a static policy | TIM and SIM approximation algorithms · Random environment | approximation error | Mixed |
| Apply the one-sided penalty structure in which agent 1 can penalize agents 2 and 3 | TIM approximation · Coin game | estimated influence of agent 1 on other agents | Helped |
| Apply the penalty structure in which agent 2 can penalize agent 3 but is not penalized by agent 3 | TIM approximation · Coin game | estimated influence of agent 2 on other agents | Mixed |
| Use the coin-game interaction where agent 3 has no direct penalties to impose | TIM approximation · Coin game | estimated influence of agent 3 on other agents | Mixed |
Surprising findings
- Larger numbers of true dependencies give a larger initial approximation error but a smaller final error, because independence can only be detected when impact samples are exactly zero and Q-approximation error causes overestimation.
Limitations
- Experiments are small-scale (random 5-agent MDP and a 3-agent coin game) and only sketch practical use.
- Estimator accuracy is limited by Q-function approximation error, which causes overestimation of influence when agents are truly independent.
- TIM and SIM are descriptive; the paper does not use them to improve learning.
Experimental setup
Datasets: random multi-agent MDP (5 agents, 5 states, binary actions) multi-agent coin game (10x10 grid, 3 agents)
Benchmarks: random multi-agent MDP multi-agent coin game
Metrics: approximation error of TIM and SIM TIM estimates per agent pair
Builds on: Zhang et al. 2018 multi-agent actor-critic coordination graphs Borkar stochastic approximation Value of Interaction
Closest papers by meaning
- Influence-Based Multi-Agent Exploration (ICLR 2020 · similarity 0.89)
- Situation-Dependent Causal Influence-Based Cooperative Multi-Agent Reinforcement Learning (AAAI 2024 · similarity 0.87)
- A Principle of Targeted Intervention for Multi-Agent Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
- O-MAPL: Offline Multi-agent Preference Learning (ICML 2025 · similarity 0.85)
- Bayesian Ego-graph inference for Networked Multi-Agent Reinforcement Learning (NeurIPS 2025 · similarity 0.85)
- Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.