The Complexity of All-switches Strategy Improvement
The Complexity of All-switches Strategy Improvement
复制标题
全交换机策略改进的复杂性
DOI：
10.23638/lmcs-14(4:9)2018
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Rahul Savani
中科院分区：
文献类型：
--
作者：
John Fearnley;Rahul Savani
策略改进是一种广泛使用的算法，用于求解基于图形的无限游戏。这些算法通过开关规则进行参数化，最自然的规则之一是“所有开关”，在每次迭代中都会尽可能多地切换边缘。继续进行最近的工作，我们从计算复杂性的角度研究了全切口策略的改进。我们认为两个自然的决策问题，两者都作为游戏G，开始策略s和一个边缘e。问题是：1。边缘开关问题，即，从s on Game G上启动时，边缘E是否曾经通过全旋转策略进行改进？ 2。最佳策略问题，即，在最终策略中使用的边缘是通过策略从s开始时通过策略改进而使用的？我们显示了以下设置的边缘开关问题和最佳策略问题的Pspace完整性：VOGE和Jurdzinski的离散策略改进算法的奇偶校验游戏；带有增益偏见算法的平均付款游戏[11，33]；以及带有标准策略改进算法的折扣游戏和简单的随机游戏。我们还显示了一个类似问题的Pspace完整性，可用于边缘开关的底部距离算法，以实现立方体上的无环唯一的下沉方向。
Strategy improvement is a widely-used and well-studied class of algorithms for solving graph-based infinite games. These algorithms are parametrized by a switching rule, and one of the most natural rules is "all switches" which switches as many edges as possible in each iteration. Continuing a recent line of work, we study all-switches strategy improvement from the perspective of computational complexity. We consider two natural decision problems, both of which have as input a game G, a starting strategy s, and an edge e. The problems are: 1. The edge switch problem, namely, is the edge e ever switched by all-switches strategy improvement when it is started from s on game G? 2. The optimal strategy problem, namely, is the edge e used in the final strategy that is found by strategy improvement when it is started from s on game G? We show PSPACE-completeness of the edge switch problem and optimal strategy problem for the following settings: Parity games with the discrete strategy improvement algorithm of Voge and Jurdzinski; mean-payoff games with the gain-bias algorithm [11, 33]; and discounted-payoff games and simple stochastic games with their standard strategy improvement algorithms. We also show PSPACE-completeness of an analogous problem to edge switch for the bottom-antipodal algorithm for Acyclic Unique Sink Orientations on Cubes.
登录
查看更多内容
DOI：
10.1007/978-3-642-20807-2_16
发表时间：
2011-06
期刊：
--
影响因子：
--
作者：
Oliver Friedmann
通讯作者：
Oliver Friedmann
最新确定性策略迭代算法的指数下界
DOI：
10.2168/lmcs-7(3:23)2011
发表时间：
2011
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
Oliver Friedmann
通讯作者：
Oliver Friedmann
DOI：
10.1007/s10009-019-00509-3
发表时间：
2019-06-01
影响因子：
1.5
作者：
Fearnley, John;Jain, Sanjay;Wojtczak, Dominik
通讯作者：
Wojtczak, Dominik
单纯形算法具有 NP 强大性
DOI：
10.1145/3280847
发表时间：
2018
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Disser;Skutella;Martin
通讯作者：
Martin