Expectations or Guarantees? I Want It All! A crossroad between games and MDPs
Expectations or Guarantees? I Want It All! A crossroad between games and MDPs
复制标题
期望还是保证？
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Jean
中科院分区：
文献类型：
--
作者：
V. Bruyère;E. Filiot;Mickael Randour;Jean
当推理一个代理的战略能力时，重要的是要考虑其对手的性质。在定量规格的控制器合成的特定背景下，通常的问题是设计一个反应系统，产生一些期望的性能，考虑到系统的环境的可能影响的策略。至少有两种方式来看待这种环境。在两人定量博弈的经典分析中，环境是纯粹对抗的，问题是提供严格的性能保证。在马尔可夫决策过程中，环境被视为纯粹随机的：目标是优化预期收益，对个人结果没有保证。在这项短暂的工作中，我们报告了最近的结果[10，9]，引入了超越最坏情况的综合问题，这是为了构建策略，保证在最坏情况下的一些定量要求，同时提供一个更高的期望值对特定的随机模型的环境作为输入。这个问题与生产在日常情况下提供良好的预期性能的系统控制器有关，同时即使在非常糟糕（虽然不太可能）的情况下也确保严格（但宽松）的性能阈值。它已被研究的平均收益和最短路径的定量措施。
When reasoning about the strategic capabilities of an agent, it is important to consider the nature of its adversaries. In the particular context of controller synthesis for quantitative specifications, the usual problem is to devise a strategy for a reactive system which yields some desired performance, taking into account the possible impact of the environment of the system. There are at least two ways to look at this environment. In the classical analysis of two-player quantitative games, the environment is purely antagonistic and the problem is to provide strict performance guarantees. In Markov decision processes, the environment is seen as purely stochastic: the aim is then to optimize the expected payoff, with no guarantee on individual outcomes. In this expository work, we report on recent results [10, 9] introducing the beyond worst-case synthesis problem, which is to construct strategies that guarantee some quantitative requirement in the worst-case while providing an higher expected value against a particular stochastic model of the environment given as input. This problem is relevant to produce system controllers that provide nice expected performance in the everyday situation while ensuring a strict (but relaxed) performance threshold even in the event of very bad (while unlikely) circumstances. It has been studied for both the mean-payoff and the shortest path quantitative measures.