Polyhedral value iteration for discounted games and energy games
Polyhedral value iteration for discounted games and energy games
复制标题
折扣游戏和能量游戏的多面体价值迭代
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
A. Kozachinskiy
中科院分区：
文献类型：
--
作者：
A. Kozachinskiy
我们提出了一种确定性算法，在强 $n^{O(1)}cdot (2 + sqrt{2})^n$ 时间内解决具有 $n$ 个节点的折扣游戏。对于二分折扣游戏的特殊情况，我们的算法运行 $n^{O(1)}cdot 2^n$ 次。在我们的工作之前，无论折扣因子如何，都无法及时运行 $2^{o(nlog n)}$ 的确定性算法。
我们将我们的方法称为多面体值迭代。我们依赖一个众所周知的事实，即折扣游戏的价值可以从所谓的最优方程中找到。在该算法中，我们考虑通过松弛最优性方程获得的多面体。我们通过每次沿着仔细选择的移位尽可能远地移动来迭代该多面体边界上的点。这一直持续到当前点满足最优方程为止。
我们的方法深受 Dorfman 等人最近的算法的启发。 （ICALP 2019）能源游戏。为了完整起见，我们以多面体值迭代的形式呈现他们的算法。与原始算法不同，我们的阐述不要求边权重为整数，并且适用于任意实数权重。
We present a deterministic algorithm solving discounted games with $n$ nodes in strongly $n^{O(1)}cdot (2 + sqrt{2})^n$-time. For a special case of bipartite discounted games our algorithm runs in $n^{O(1)}cdot 2^n$-time. Prior to our work no deterministic algorithm running in time $2^{o(nlog n)}$ regardless of the discount factor was known.
We call our approach polyhedral value iteration. We rely on a well-known fact that the values of a discounted game can be found from the so-called optimality equations. In the algorithm we consider a polyhedron obtained by relaxing optimality equations. We iterate the points on the border of this polyhedron by moving each time along a carefully chosen shift as far as possible. This continues until the current point satisfies optimality equations.
Our approach is heavily inspired by a recent algorithm of Dorfman et al. (ICALP 2019) for energy games. For completeness, we present their algorithm in terms of polyhedral value iteration. Our exposition, unlike the original algorithm, does not require edge weights to be integers and works for arbitrary real weights.