Trading performance for stability in Markov decision processes

作者：

Highlights：

• We show that optimizing mean payoff and stability requires memory and randomization.

• We show how to reduce existence of optimal strategies to a constrained problem.

• We give a complexity classification for the problem of finding an optimal strategy.

摘要

•We show that optimizing mean payoff and stability requires memory and randomization.•We show how to reduce existence of optimal strategies to a constrained problem.•We give a complexity classification for the problem of finding an optimal strategy.

论文关键词：Markov decision processes,Mean payoff,Stability,Stochastic systems,Controller synthesis

论文评审过程：Received 9 February 2016, Revised 16 July 2016, Accepted 21 September 2016, Available online 19 October 2016, Version of Record 14 November 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.09.009