论文标题
策略迭代的晶格理论观点
A Lattice-Theoretical View of Strategy Iteration
论文作者
论文摘要
策略迭代是一种经常用于两人游戏的技术，以确定获胜者或计算收益，但据我们所知，尚未考虑策略迭代的一般框架。受到简单随机游戏的先前工作的启发，我们提出了策略迭代的一般形式化，以基于MV链的一类合适的完整晶格求解最小的固定点方程。我们设计了可用于分别表示为所谓的最小分数的非强度固定点功能的算法。相应地，我们开发了两种不同的技术：来自上方的策略迭代，这必须解决迭代可能到达最不重要的fixpoint的问题，从下方开始，这是算法更简单的，但需要更涉及的正确性参数。我们应用我们的方法来解决能源游戏并计算概率自动机的行为指标。
Strategy iteration is a technique frequently used for two-player games in order to determine the winner or compute payoffs, but to the best of our knowledge no general framework for strategy iteration has been considered. Inspired by previous work on simple stochastic games, we propose a general formalisation of strategy iteration for solving least fixpoint equations over a suitable class of complete lattices, based on MV-chains. We devise algorithms that can be used for non-expansive fixpoint functions represented as so-called min-, respectively, max-decompositions. Correspondingly, we develop two different techniques: strategy iteration from above, which has to solve the problem that iteration might reach a fixpoint that is not the least, and from below, which is algorithmically simpler, but requires a more involved correctness argument. We apply our method to solve energy games and compute behavioural metrics for probabilistic automata.
