be different for different pairs of agents due to a variety of reasons (e.g., the difference of agents’ capabilities and preferences, and the difference of interaction timing and locations) in practical scenarios. For example, in sensor networks [@zhang2013coordinating], the overlapping scanning areas of each pair of sensors are of various importance and different rewards are obtained when specific scanning areas are coordinated between two senor agents. Another example is that in negotiation domain [@baarslag2015optimal], an agent may have different preferences on each offer provided by different opponents. Therefore, in this paper, we relax this assumption by assuming that the payoff matrix between each pair of agents is different which is generated from certain probability distribution, and the payoff information is unknown before their interaction.

Second, the network topologies can be dynamic. For example in social networks [@ellison2007benefits; @kwak2010twitter], it is common that users follow and unfollow other users on their own initiative due to individual preference and interest. Therefore, in this paper, we consider a dynamic environment where each agent is given the opportunities to change its connections through rewiring to interact with agents which may bring higher payoffs during the course of interactions. The rewiring mechanism has been previously 