用强化学习让多个智能体在局部信息下高效找路径。
Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategies
- 多智能体协作，只看局部网络信息
- 在真实社交网络上路径搜索成功率超基线30%以上
- 适合大规模动态社交网络场景
图路径搜索是经典计算机科学问题，近年因强化学习（RL）有望超越传统方法而受到关注。现有RL方法通常依赖全局网络视图，不适用于大规模、动态且隐私敏感的场景。社交网络中的搜索尤为关键。受实验社会学启发，我们提出一种多智能体协作框架，各智能体仅拥有局部网络视图。该方法有效利用同质性与结构异质性，在合成和真实社交网络上的实验表明，模型显著优于学习型与启发式基线。此外，结果表明可通过奖励驱动学习构建有意义的图导航嵌入。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。