Can RL agents find paths in social networks without global knowledge?
Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategies
September 13, 2024
https://arxiv.org/pdf/2409.07932This paper explores how to efficiently find paths in a graph using multiple decentralized agents, particularly within social networks. The agents only have a limited, local view of the network and must cooperate to find the shortest path to a target node.
This is relevant to LLM-based multi-agent systems as it proposes:
- Using a central LLM (GARDEN) during training to learn effective message passing strategies based on node attributes and local graph structure. This LLM combines Graph Attention Networks and Reinforcement Learning.
- Deploying decentralized agents that leverage the learned strategies and local information for efficient pathfinding, similar to how humans navigate social networks.
- This approach enables LLMs to discover "hidden metrics" for efficient navigation within graphs, potentially outperforming classic algorithms relying solely on explicit features.