The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes
证明了最高增益/最负简约成本转轴规则的单纯形法在确定性马尔可夫决策过程中，无论折扣因子如何，都在强多项式时间内收敛，对n状态m动作的均匀折扣情形迭代次数为O(n^3 m^2 log^2 n)。
We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (MDPs) regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n 3 m 2 log 2 n) iterations if the discount factor is uniform and O(n 5 m 3 log 2 n) iterations if each action has a distinct discount factor. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from 1.