mlsanityData to 14 Oct 2026

Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategies

arXiv 2409.07932 ↗First posted 12 Sep 2024cs.LG cs.AI cs.MAcited by 0

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

Graph path search is a classic computer science problem that has been recently approached with Reinforcement Learning (RL) due to its potential to outperform prior methods. Existing RL techniques typically assume a global view of the network, which is not suitable for large-scale, dynamic, and privacy-sensitive settings. An area of particular interest is search in social networks due to its numerous applications. Inspired by seminal work in experimental sociology, which showed that decentralized yet efficient search is possible in social networks, we frame the problem as a collaborative task between multiple agents equipped with a limited local view of the network. We propose a multi-agent approach for graph path search that successfully leverages both homophily and structural heterogeneity. Our experiments, carried out over synthetic and real-world social networks, demonstrate that our model significantly outperforms learned and heuristic baselines. Furthermore, our results show that meaningful embeddings for graph navigation can be constructed using reward-driven learning.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 16 of its 52 references that are in the map. First posted on arXiv 12 Sep 2024.

Builds on

16 of 52 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective9 Apr

Other references · 15

  1. 2017Graph Attention Networkscited by 8,923
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  3. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,558
  4. 2017Counterfactual Multi-Agent Policy Gradientscited by 751
  5. 2017Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learningcited by 161
  6. 2019Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use casecited by 53
  7. 2015Traversing Knowledge Graphs in Vector Spacecited by 51
  8. 2018Experience-driven Networking: A Deep Reinforcement Learning based Approachcited by 41
  9. 2017Learning Heuristic Search via Imitationcited by 34
  10. 2018M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Searchcited by 34
  11. 2021Learning to Walk with Dual Agents for Knowledge Graph Reasoningcited by 16
  12. 2020CFR-RL: Traffic Engineering with Reinforcement Learning in SDNcited by 12
3 more
  1. 2021GDDR: GNN-based Data-Driven Routingcited by 9
  2. 2022Learning Graph Search Heuristicscited by 7
  3. 2023Intrinsically motivated graph exploration using network theories of human curiositycited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Scaling Team Coordination on Graphs with Reinforcement Learning
  2. 2024Towards Generalizability of Multi-Agent Reinforcement Learning in Graphs with Recurrent Message Passing
  3. 2026The Role of Network Topology and Opponent Information in Shaping Cooperation in Multi-Agent Reinforcement Learning Systems
  4. 2026PC2P: Multi-Agent Path Finding via Personalized-Enhanced Communication and Crowd Perception
  5. 2026Collaborative Spatial Learning with Multi-LLM Agents in Networked Social Experiments
  6. 2025Bayesian Ego-graph Inference for Networked Multi-Agent Reinforcement Learning
  7. 2025Reinforcement Networks: novel framework for collaborative Multi-Agent Reinforcement Learning tasks
  8. 2024Graph Enhanced Reinforcement Learning for Effective Group Formation in Collaborative Problem Solving