Learning-Based Control of the Consensus Value in Unknown Graphs

We consider the problem of optimal budget allocation for consensus reaching in unknown networks. The network is represented by a directed graph whose vertices corresponds to agents influencing each other. At discrete instants, agents are influenced by an external entity that intends to sway the consensus to a target value. Between two external influence instants, the states of the agents evolve continuously due to the network dynamics. Prior results establish that, in known networks, a water-filling strategy that targets the most influential agents first is optimal. In our approach to the unknown-network setup, the marketer uses the evolution between two influence instants to update a learned model of the graph. Then, the control allocation at the next marketing instant is done according to the water-filling strategy applied to the current model of the graph. Our main analytical contribution states that the sub-optimality of the budget allocation induced by the approximation of the graph is related to the error of the learning algorithm. Extensive numerical analysis illustrates the performance of our method and suggests a regularization term that improves it further.