used to explore indirect reciprocity [@peleteiro2014exploring] or cope with cheaters [@griffiths2010changing] to promote cooperations among agents in non-cooperative environments such as $Donation$ games. In contrast, in this paper, we focus on cooperative environments where agents can utilize the rewiring mechanism to increase their benefits in long-run interactions by breaking connections to bad-performance neighbors and replacing them with new connections.

In this work, during each round, each agent goes through two main phases: the rewiring phase and the interaction phase. In the rewiring phase, each agent is likely to be given the opportunity to alter their connections through rewiring for higher payoffs in future interactions. The key problem here is how to compute the optimal rewiring strategy to maximize the long-run interaction payoff against the network dynamics. To make efficient rewiring decisions, each agent has to take two aspects of uncertainties into consideration, i.e., the uncertainties of opponents’ behaviors and the payoff matrix with unknown peers. To this end, we model an agent’s rewiring problem as a sequential decision-making problem and propose an optimal rewiring approach for agents to select most beneficial peers among all reachable agents. In the interaction phase, agents learn their policies from pair-wise interactions through playing certain 