An Optimal Rewiring Strategy for Reinforcement Social Learning in Cooperative Multiagent Systems

Hongyao Tang, Li Wang, Zan Wang, Tim Baarslag, Jianye HaoarXiv 2018 · arXiv

Introduction

In Multiagent Systems (MAS), coordination is often achieved through social learning, where agents interact with local neighbors to discover mutually beneficial strategies. Traditional models typically assume static network topologies and uniform payoff structures. However, real-world scenarios involve fluid social connections and heterogeneous coordination benefits. This paper addresses these limitations by introducing an optimal rewiring strategy that allows agents to dynamically manage their interaction partners in environments with uncertain payoffs.

The Social Learning Framework with Optimal Rewiring

The proposed framework integrates a dynamic rewiring mechanism with reinforcement learning. The interaction protocol for each agent follows a structured sequence of decision-making and learning phases.

Algorithm 1: The overall interaction protocol for agents under the social learning framework.

Rewiring Phase

Agents periodically evaluate their current social circle. The decision to break a connection with a poorly performing neighbor and establish a new one is modeled as a Markov Decision Process (MDP). To solve this efficiently, the authors adapt Pandora’s Rule from search theory. Agents calculate a "K-sight" index ($\Lambda$) for potential partners, representing the expected net benefit of a new connection over the next $K$ rounds, factoring in the cost ($c$) of rewiring. An agent only rewires if the potential gain from a new peer exceeds the utility of its current worst-performing neighbor.

Interaction Phase

Following the rewiring decision, agents engage in a 2-action cooperative game with a randomly selected neighbor. The payoffs for successful coordination (actions $a,a$ or $b,b$) are stochastic variables ($u_a, u_b$), while miscoordination results in a lower reward ($\alpha$). Agents update their internal policies and action models using reinforcement learning algorithms such as Fictitious Play (FP), Joint-Action Learner (JAL), or Joint-Action WoLF-PHC.

Experimental Evaluation

The strategy was tested in simulated environments with varying network topologies, including Regular, Small-world, and Scale-free networks, with populations up to 1,000 agents. Payoffs were sampled from Uniform or Beta distributions to simulate environmental uncertainty. The "Optimal" strategy was benchmarked against Random rewiring and K-HE (K-sight Highest Expectation), a strategy that ignores the baseline utility of current neighbors.

Key Results and Discussion

The Optimal strategy consistently outperformed benchmarks across diverse environment types and rewiring costs. A critical finding is the "K-sight" trade-off: the parameter $K$ must be carefully balanced against the rewiring cost $c$. If $K$ is too small, agents are overly cautious; if $K$ is too large, they become over-optimistic, chasing marginal gains that do not justify the costs.

Average reward comparison between the Optimal strategy and K-HE across different agent proportions and c/K ratios.

As shown in the experimental results, the Optimal strategy maintains superior average rewards regardless of the proportion of K-HE agents in the population. Furthermore, the system's performance proved robust to initial network structures, as dynamic rewiring eventually reshaped the networks into configurations optimized for the specific payoff distributions.

Conclusion and Future Work

This research demonstrates that an MDP-based rewiring strategy using the K-sight index significantly enhances coordination and reward maximization in cooperative MAS. Future work will explore extending this framework to non-cooperative or competitive systems, incorporating network-aware strategies (e.g., identifying hubs), and modeling variable costs for breaking long-standing versus new connections.

Summary updated

Abstract

Multiagent coordination in cooperative multiagent systems (MASs) has been widely studied in both fixed-agent repeated interaction setting and the static social learning framework. However, two aspects of dynamics in real-world multiagent scenarios are currently missing in existing works. First, the network topologies can be dynamic where agents may change their connections through rewiring during the course of interactions. Second, the game matrix between each pair of agents may not be static and usually not known as a prior. Both the network dynamic and game uncertainty increase the coordination difficulty among agents. In this paper, we consider a multiagent dynamic social learning environment in which each agent can choose to rewire potential partners and interact with randomly chosen neighbors in each round. We propose an optimal rewiring strategy for agents to select most beneficial peers to interact with for the purpose of maximizing the accumulated payoff in repeated interactions. We empirically demonstrate the effectiveness and robustness of our approach through comparing with benchmark strategies. The performance of three representative learning strategies under our social learning framework with our optimal rewiring is investigated as well.
BibTeX
@misc{tang2018optimal,
  author = {Hongyao Tang and Li Wang and Zan Wang and Tim Baarslag and Jianye Hao},
  title = {{An Optimal Rewiring Strategy for Reinforcement Social Learning in Cooperative Multiagent Systems}},
  year = {2018},
  eprint = {1805.08588},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.08588},
}
Figure