TD($\lambda$)-GA: A Reinforcement Learning-Based Game Algorithm for Weighted Vertex Cover of Networks

Weighted vertex cover (WVC) problem, as one of the most important combinatorial optimization problems, is a general form of the classic vertex cover problem. The existing researches focused on the solution quality but ignoring the time efficiency, which makes their tradeoff be a technical challenge. In this paper, we first reformulate the WVC problem as an asymmetric snowdrift game on weighted networks. Then, we propose a new game-based algorithm by combining temporal difference method in reinforcement learning, that is, the temporal-difference(λ)- based game algorithm (TD(λ)-GA), which can achieve a balance between the running time and the solution quality. Finally, we perform numerical simulations to demonstrate that the proposed algorithm can find a high-quality solution within reasonable runtime by comparing it with other representative optimization algorithms.