Limits of multi-discounted Markov decision processes

Markov decision processes (MDPs) are controllable dis-crete event systems with stochastic transitions. The pay-off received by the controller can be evaluated in differ-ent ways, depending on the payoff function the MDP is equipped with. For example a mean–payoff function eval-uates average performance, whereas a discounted pay-off function gives more weights to earlier performance by means of a discount factor. Another well–known example is the parity payoff function which is used to encode logical specifications [14]. Surprisingly, parity and mean–payoff MDPs share two non–trivial properties: they both have pure stationary op-timal strategies [4, 15] and they both are approximable by discounted MDPs with multiple discount factors (multi– discounted MDPs) [5, 15]. In this paper we unify and generalize these results. We introduce a new class of payoff functions called the priority weighted payoff functions, which are generalization of both parity and mean–payoff functions. We prove that priority weighted MDPs admit optimal strategies that are pure and stationary, and that the priority weighted value of an MDP is the limit of the multi–discounted value when discount fac-tors tend to 0 simultaneously at various speeds. 1