An approach for determining the optimal strategies for an average Markov decision problem with finite state and action spaces

Dmitrii Lozovanu^a, Stefan Pickl<sup>b

a</sup> Institute of Mathematics and Computer Science, 5 Academiei str., Chişinău, MD-2028 Moldova
^b Institute for Theoretical Computer Science, Mathematics and Operations Research, Universität der Bundeswehr München, 85577 Neubiberg-München, Germany

Abstract: The average reward Markov decision problem with finite state and action spaces is considered and an approach for determining the optimal pure and mixed stationary strategies for this problem is proposed. We show that the considered problem can be formulated in terms of stationary strategies where the objective function is quasi-monotonic (i.e. it is quasi-convex and quasi-concave) on the feasible set of stationary strategies. Using such a quasi-monotonic programming model with linear constraints we ground algorithms for determining the optimal pure and mixed stationary strategies for the average Markov decision problem.

Keywords and phrases: Markov decision processes, average optimization criterion, stationary strategies, optimal strategies.

MSC: 90C15, 90C40

Received: 27.12.2017

Language: English