Vector-valued Markov decision processes and systems of linear inequalities

For a vector-valued Markov decision process, the paper characterizes optimal (deterministic) stationary policies by systems of linear inequalities and presents an algorithm for finding all optimal stationary policies from among all randomized, history-remembering ones. The algorithm consists of improving the policies and of checking the optimality of a policy by solving the associated system of linear inequalities via Fourier elimination.