Source-linked AI summary
Influence-Based Multi-Agent Exploration
Tonghan Wang, Jianhao Wang, Yi Wu, Chongjie Zhang
TL;DR
The paper addresses the limited study of exploration in transition-dependent cooperative multi-agent settings. It introduces EITI and EDTI, influence-based exploration methods optimized for policy-gradient learning, and reports effective discovery of influential states across sparse-reward cooperative tasks. The methods assume centralized access to other agents’ information during training while execution remains decentralized.
Problem
Exploration methods for sparse-reward cooperative tasks with complex reward and transition dependencies among agents remain largely unstudied.
Method
EITI uses mutual information over transition dynamics, while EDTI uses Value of Interaction to quantify effects on other agents’ expected returns and optimize influence-based exploration regularizers.
Results
Across varied sparse-reward cooperative tasks, EITI and EDTI discover influential states, with EDTI additionally filtering interactions that have no performance effects.
Takeaways & Limitations
Influential states can function as implicitly discovered subgoals that guide and coordinate multi-agent exploration.
Takeaways & Limitations
The approach uses centralized training with access to other agents’ information, while decentralized execution provides only individual states or local observations.
Abstract
from arXiv · showhide
Intrinsically motivated reinforcement learning aims to address the exploration challenge for sparse-reward tasks. However, the study of exploration methods in transition-dependent multi-agent settings is largely absent from the literature. We aim to take a step towards solving this problem. We present two exploration methods: exploration via information-theoretic influence (EITI) and exploration via decision-theoretic influence (EDTI), by exploiting the role of interaction in coordinated behaviors of agents. EITI uses mutual information to capture influence transition dynamics. EDTI uses a novel intrinsic reward, called Value of Interaction (VoI), to characterize and quantify the influence of one agent's behavior on expected returns of other agents. By optimizing EITI or EDTI objective as a regularizer, agents are encouraged to coordinate their exploration and learn policies to optimize team performance. We show how to optimize these regularizers so that they can be easily integrated with policy gradient reinforcement learning. The resulting update rule draws a connection between coordinated exploration and intrinsic reward distribution. Finally, we empirically demonstrate the significant strength of our method in a variety of multi-agent scenarios.
1 INTRODUCTION
The paper addresses sparse-reward exploration in transition-dependent cooperative multi-agent settings by coordinating agents through interaction-based influence. It proposes EITI and EDTI, optimizes them with policy-gradient-compatible regularizers, and evaluates them across sparse-reward cooperative tasks.
- Multi-agent exploration remains largely unstudied for cooperative settings with complex reward and transition dependencies.
- The approach coordinates decentralized curiosity-driven exploration by encouraging agents to visit interaction points that can influence other agents’ exploration.Interaction points are described as critical state-action configurations that can lead to important under-explored regions.
- EITI uses mutual information to capture interdependence between agents’ transition dynamics.
- EDTI uses Value of Interaction to quantify how one agent’s behavior affects other agents’ expected intrinsic and extrinsic returns.
- Augmented policy-gradient formulations estimate the EITI and EDTI gradients from trajectories and connect coordinated exploration with intrinsic-reward distribution.
- Across varied sparse-reward cooperative tasks, EITI and EDTI discover influential states, while EDTI filters interactions without performance effects.The paper also interprets influential states as implicitly discovered subgoals that guide and coordinate exploration.
2 RELATED WORKS
Prior exploration work has achieved stronger progress in single-agent and transition-independent multi-agent settings than in general transition-dependent cooperative environments. This paper builds on intrinsic rewards, influence modeling, and mutual-information methods to address that broader setting.
- Single-agent exploration has produced provably efficient methods and intrinsic-reward approaches, but some methods scale poorly to large or continuous settings.
- Existing multi-agent exploration studies mainly address transition-independent settings, including coverage, repeated single-stage, and decentralized-curiosity problems.
- Related multi-agent intrinsic-reward work models how one agent influences other agents’ decision-making processes.The paper distinguishes its focus on influence over other agents’ transition functions and rewarding structure.
- Mutual information has been applied to intrinsically motivated single-agent exploration and to multi-agent intention sharing and hiding.
3 SETTINGS
The paper models fully cooperative tasks as factored multi-agent MDPs with joint states, actions, transitions, shared extrinsic rewards, and a finite horizon. Agents train centrally with other agents’ information but execute using only individual states.
- A factored multi-agent MDP contains a finite agent set, joint state and action spaces, transition function, shared reward, and horizon.
- Each agent selects an action from its local state, while the joint action determines the shared extrinsic reward and next state through the transition function.
- The joint policy is intended to maximize team performance through the agents’ coordinated decisions.The objective is expressed using joint action-value and value functions over episode trajectories.
- Centralized training provides access to other agents’ states, actions, intrinsic rewards, and value functions, whereas decentralized execution requires only individual states.
4 INFLUENCE-BASED COORDINATED MULTI-AGENT EXPLORATION
The framework coordinates multi-agent exploration by rewarding interactions that influence other agents’ transitions or expected returns. It introduces EITI and EDTI, then derives trajectory-based policy-gradient optimization for these influence objectives.
- Framework: Curiosity drives individual exploration, but the framework adds an influence value to encourage agents to visit interaction points that affect others’ exploration.The overall objective combines intrinsic curiosity with an influence term weighted by β.
- EITI: EITI measures transition interactions with mutual information between one agent’s next state and another agent’s state-action pair.Optimizing MI encourages an agent to visit critical points where it can influence the other agent’s transition probability.
- Optimization: Augmented policy-gradient formulations estimate the influence objectives from sampled trajectories despite policy-dependent stationary distributions.The resulting update connects coordinated exploration with the distribution of individual intrinsic rewards among team members.
- EITI: EITI rewards state-action pairs that influence another agent’s trajectory, while assigning zero reward under transition independence.During centralized training, agents can use other agents’ states and actions; execution uses only local observations.
- EDTI: EDTI defines Value of Interaction as the expected difference between another agent’s action value and its counterfactual value without the influencing state and action.Unlike MI, VoI captures both transition and reward influence through action values containing intrinsic and extrinsic rewards.
- EDTI: VoI emphasizes interactions that support future value and can filter interactions that do not lead to extrinsic reward after intrinsic reward diminishes.The counterfactual formulation also filters noise from global and other agents’ intrinsic reward signals when assessing individual contribution.
5 EXPERIMENTAL RESULTS
Experiments evaluate EITI and EDTI on didactic and complex sparse-reward cooperative tasks, testing interaction-point discovery, exploration, and EDTI’s filtering of irrelevant interactions. Across these settings, both methods facilitate exploration, while EDTI is especially effective when only some interactions lead to external rewards.
- Evaluation setup: Experiments use five random seeds with 95% confidence intervals and compare EITI and EDTI against intrinsic-reward, centralized, and other ablation baselines.The evaluation uses PPO and tests whether the methods capture interaction points, improve learning, and filter interactions unrelated to environmental rewards.
- Didactic examples: EITI and EDTI learn the winning strategy more efficiently than the baselines in the pass task by highlighting interaction points during exploration.EITI and EDTI rewards identify interaction points at different stages, encouraging agents to revisit configurations that support the goal strategy.
- Didactic examples: EDTI outperforms EITI in secret-room because it highlights the two valuable interaction pairs while EITI treats three doors equally.The task contains six interaction-point pairs, but only two are related to external rewards; EDTI filters the irrelevant interactions as its intrinsic reward diminishes.
- Complex tasks: In push-box, EITI and EDTI are considerably more successful than the struggling baselines because joint pushing creates interaction-based intrinsic rewards.The agents must coordinate positions and actions over multiple steps, and the box moves only when both agents push in the same direction simultaneously.
- Complex tasks: In island, the methods help agents discover collective beast attacks despite the locally optimal strategy of collecting treasures.The methods provide intrinsic incentives for agents to enter the beast’s attack range together, and they learn to catch the beast quickly.
- Overall findings: Large-island results show that the methods handle settings with more than two agents, while overall EITI is stronger when all interactions align with extrinsic rewards and EDTI otherwise performs better.The paper attributes EDTI’s advantage in other tasks to filtering interaction points that cannot lead to greater value.
6 CLOSING REMARKS
The paper proposes EITI and EDTI as influence-based methods for coordinated multi-agent exploration, using MI and VoI to distribute exploration incentives. The methods support decentralized policy-gradient optimization and are evaluated on intrinsic EDTI across several tasks.
- EITI uses mutual information, while EDTI uses Value of Interaction to measure agents’ influence on one another’s exploration processes.VoI captures both transition and reward influence and includes intrinsic and extrinsic rewards.
- The methods use policy-gradient optimization to achieve coordinated exploration in a decentralized manner and optimize team performance.The update formulation connects coordinated exploration with the distribution of individual intrinsic rewards.
- Intrinsic VoI distributes individual curiosity among team members by encouraging agents to help one another reach under-explored states.
- Intrinsic EDTI was evaluated against EITI and EDTI on pass, secret-room, push-box, and island.
B.1 GRADIENT OF MUTUAL INFORMATION
This section explains how mutual information is optimized to encourage agents to influence one another’s transition dynamics. It introduces the related Value of Interaction formulation and its trajectory-based theoretical development.
- Mutual information between agents’ trajectories is optimized to encourage agents to exert influence on one another’s transitions.
- Value of Interaction captures transition and reward interactions and is defined as an expectation over trajectories for the two-agent case.This trajectory form supports the derivation of the EDTI policy-gradient update.
- Theorem 1 defines the Value of Interaction of agent 1 on agent 2, with the derivation using counterfactual immediate rewards and value functions.
B.3 CALCULATING GRADIENT OF VOI
This section develops optimization and estimation procedures for Value of Interaction. It uses empirical transition distributions for small spaces and variational inference as a more scalable alternative, with some noise and slower learning.
- The EDTI optimization derives a target function and corresponding gradient terms for optimizing Value of Interaction with respect to policy parameters.
- Mutual information and Value of Interaction require estimates of transition distributions conditioned on individual and joint state-action information.
- Empirical transition frequencies are substituted for the corresponding distribution terms in the MI and VoI equations.
- Monte Carlo sampling uses visitation counts for small spaces, whereas variational inference learns neural-network distributions for larger spaces.Monte Carlo sampling can consume large memory as the problem space grows.
- Variational inference introduces noise in EDTI reward estimation and requires slightly more steps to learn the true probability and strategy than Monte Carlo sampling.
D.1 NETWORK ARCHITECTURE, HYPERPARAMETERS, AND INFRASTRUCTURE
The experiments use PPO2 with visitation-count exploration bonuses and task-specific scaling weights. The implementation also includes a three-layer variational-inference network and evaluates tasks including push-box, island, and large-island.
- Experiments use OpenAI PPO2 with default parameters, 32 parallel environments, and an NVIDIA RTX 2080TI GPU.
- The intrinsic exploration bonus is η/N(s) for the N(s)-th visit to state s.
- Table 2 reports task-specific scaling weights for intrinsic reward terms, including βT, βint, βext, βr, βplusV int, and βplusV ext.
- The reported task set includes push-box, island, and large-island.
- The variational-inference network is a three-layer fully connected model with a 64-dimensional reparameterization estimator.It uses ReLU in the first two layers, Adam with learning rate 1 × 10^-3, and batchsize 2048.
D.2 TASK STRUCTURE
The paper evaluates coordination and exploration in sparse-reward multi-agent tasks with varying interaction structures, including navigation, pushing, and hunting scenarios. Experiments compare methods against baselines and ablations on these environments.
- Secret-room: Secret-room extends Pass to four rooms and switches, with only the desired room linked to the extrinsic team reward.The left switch opens three doors, while each room's local switch controls its own door; the grid is 25×25.
- Push-ball: Push-ball requires two agents to push a heavy box simultaneously in the same direction until it reaches a wall.The 15 × 15 task provides a team reward of 1000 only when the box is placed against the wall.
- Island: Island tests hunting and risk-sensitive coordination between two agents facing a beast, attack interactions, health loss, treasures, and a larger reward for catching it.Nine treasures each trigger a team reward of 10, while catching the beast gives 300; Figure 9 tracks catching probability and treasures over 9000 PPO updates.
- Evaluation: Figures 8 and 9 compare the proposed methods with baselines, while Figure 9 also includes ablations using catching probability and averaged treasures collected.Figure 8 covers Push-box and Island; Figure 9 focuses on Island.
- Large-island: Large-island increases the Island scale to four agents, sixteen treasures, and a beast with 16 energy and a reward of 600.The episode horizon is 300 timesteps across all tasks.