Optimally solving Markov decision processes with total expected discounted reward function: Linear programming revisited

•Compared computational performance of linear programming and the policy iteration.•Considered only discrete-time infinite-horizon MDPs with discounted reward.•Used randomly generated test problems and a real-life health-care problem.•Showed that, unlike previously reported, barrier methods for LP provide a viable tool.•LP is more effective when the transition probability matrix has a diagonal structure.

We compare the computational performance of linear programming (LP) and the policy iteration algorithm (PIA) for solving discrete-time infinite-horizon Markov decision process (MDP) models with total expected discounted reward. We use randomly generated test problems as well as a real-life health-care problem to empirically show that, unlike previously reported, barrier methods for LP provide a viable tool for optimally solving such MDPs. The dimensions of comparison include transition probability matrix structure, state and action size, and the LP solution method.