On efficiency of linear programming applied to discounted Markovian decision problems

Linear programming is known as a tool for discounted Markovian decision problems, but there are only a few numerical experiences. If the simplex method is used, the entries of the tableau can be described in terms of stochastic dynamic optimization, too. A simplex method which exploits the special structure of linear programs corresponding to discounted Markovian decision problems turns out to be efficient for problems with (i) discounting factors close to unity and high accuracy, and (ii) either not too large state spaces or periodically structured transition probability matrices.