Optimal sequential stochastic shortest path interdiction
研究领导者与追随者在网络阻断中的周期性互动，领导者通过多臂老虎机框架选择阻断弧集以最大化追随者的累积路径成本，并提出了适应线性老虎机的策略。
We consider the periodic interaction between a leader and a follower in the context of network interdiction where, in each period, the leader first blocks (momentarily) passage through a subset of arcs in a network, and then the follower traverses the shortest path in the interdicted network. We assume that arc costs are stochastic and that while their underlying distribution is known to the follower, it is not known by the leader. We cast the problem of the leader, who aims at maximizing the cumulative cost incurred by the evader, using the multi-armed bandit framework. Such a setting differs from the traditional bandit in that the feedback elicited by playing an arm is the reaction of an adversarial agent. After developing a fundamental limit in the achievable performance by any admissible policy, we adapt traditional policies developed for linear bandits to our setting. We show that a critical step in such an adaptation is to ensure that the cost vectors imputed by these algorithms lie within a polyhedron characterizing information that can be collected without noise and in finite time. Within such a polyhedron, the problem can be mapped into a linear bandit. The polyhedron has exponentially many constraints in the worst case, which are indirectly tackled by solving several mathematical programs. We test the proposed policies and relevant benchmarks through a set of numerical experiments. Our results show that the adapted policies can significantly outperform the performance of the base policies at the price of increasing their computational complexity.