Sequential Interdiction with Incomplete Information and Learning
Sequential Interdiction with Incomplete Information and Learning
复制标题
DOI：
10.1287/opre.2018.1773
复制
发表时间：
2019-01-01
影响因子：
2.7
通讯作者：
Saure, Denis
中科院分区：
文献类型：
--
作者：
Borrero, Juan S.;Prokopyev, Oleg A.;Saure, Denis
我们提出了一个框架，一类顺序决策问题的背景下，一般的阻断问题，其中的领导者和追随者反复互动。在每个阶段，领导者分配资源来破坏追随者的表现（例如，在防御者-攻击者或网络阻断问题中），反过来，他们在一组取决于领导者决策的活动上最小化一些成本函数。虽然追随者对追随者的问题有完整的知识，但领导者只有部分信息，需要从追随者的行动产生的反馈中了解成本参数、可用资源和追随者的活动。我们衡量政策的时间稳定性方面的表现，定义为周期数的领导者匹配的行动与完整的信息的预言。特别是，我们提出了一类贪婪和强大的政策，并表明这些政策是弱最优的，最终匹配的预言机的行动，并提供了一个实时的最优性证书。我们还研究了一个半预言的概念的基础上的任何政策性能的下限。我们的数值实验表明，所提出的政策始终优于一个合理的基准，并执行相当接近的semioracle。
We present a framework for a class of sequential decision-making problems in the context of general interdiction problems, in which a leader and a follower repeatedly interact. At each period, the leader allocates resources to disrupt the performance of the follower (e.g., as in defender-attacker or network interdiction problems), who, in turn, minimizes some cost function over a set of activities that depends on the leader's decision. Although the follower has complete knowledge of the follower's problem, the leader has only partial information and needs to learn about the cost parameters, available resources, and the follower's activities from the feedback generated by the follower's actions. We measure policy performance in terms of its time-stability, defined as the number of periods it takes for the leader to match the actions of an oracle with complete information. In particular, we propose a class of greedy and robust policies and show that these policies are weakly optimal, eventually match the oracle's actions, and provide a real-time certificate of optimality. We also study a lower bound on any policy performance based on the notion of a semioracle. Our numerical experiments demonstrate that the proposed policies consistently outperform a reasonable benchmark and perform fairly close to the semioracle.