Mastering Percolation-like Games with Deep Learning
This provides a new approach to understand network robustness, with potential applications to other discrete processes in disordered systems.
The paper tackled the problem of intentional network destruction by an intelligent agent, which was not tractable with previous methods, by developing a reinforcement learning approach using deep Q-learning that successfully learns to optimally attack a network in a percolation-like game, finding that different robustness definitions induce different strategies.
Though robustness of networks to random attacks has been widely studied, intentional destruction by an intelligent agent is not tractable with previous methods. Here we devise a single-player game on a lattice that mimics the logic of an attacker attempting to destroy a network. The objective of the game is to disable all nodes in the fewest number of steps. We develop a reinforcement learning approach using deep Q-learning that is capable of learning to play this game successfully, and in so doing, to optimally attack a network. Because the learning algorithm is universal, we train agents on different definitions of robustness and compare the learned strategies. We find that superficially similar definitions of robustness induce different strategies in the trained agent, implying that optimally attacking or defending a network is sensitive the particular objective. Our method provides a new approach to understand network robustness, with potential applications to other discrete processes in disordered systems.