In this paper we introduce polytopal stochastic games, an extension of two-player, zero-sum, turn-based stochastic games, in which we may have uncertainty over the transition probabilities.  In these games the uncertainty over the probability distributions is captured via linear (in)equalities whose space of solutions forms a polytope. We give a formal definition of these games and prove their basic properties: determinacy and existence of optimal memoryless and deterministic strategies. We do this for reachability and different types of reward objectives and show that the solution exists in a finite representation of the game. We also state that the corresponding decision problems are in \(\textsf{NP}\cap \textsf{coNP}\) . We motivate the use of polytopal stochastic games via a simple example.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Polytopal Stochastic Games

  • Pablo F. Castro,
  • Pedro R. D’Argenio

摘要

In this paper we introduce polytopal stochastic games, an extension of two-player, zero-sum, turn-based stochastic games, in which we may have uncertainty over the transition probabilities.  In these games the uncertainty over the probability distributions is captured via linear (in)equalities whose space of solutions forms a polytope. We give a formal definition of these games and prove their basic properties: determinacy and existence of optimal memoryless and deterministic strategies. We do this for reachability and different types of reward objectives and show that the solution exists in a finite representation of the game. We also state that the corresponding decision problems are in \(\textsf{NP}\cap \textsf{coNP}\) . We motivate the use of polytopal stochastic games via a simple example.