We introduce the Random Walk Interdiction problem, a stochastic variant of the classical shortest-path interdiction framework in which an attacker follows a Markovian random walk toward a target node and the defender decides which nodes in the graph it should protect, and therefore stop the attacker. We first design a message-passing algorithm to compute a provable approximate solution of the problem and then we construct a randombasis representation that enables approximated solution learning through an efficient stochastic gradient ascent. Numerical experiments on synthetic directed acyclic graphs confirm that the proposed learning scheme rapidly converges to near-optimal interdiction strategies while remaining computationally scalable.
Reiffers-Masson et al. (Thu,) studied this question.