  This paper discusses algorithms for solving Markov decision processes (MDPs)
that have monotone optimal policies. We propose a two-stage alternating convex
optimization scheme that can accelerate the search for an optimal policy by
exploiting the monotone property. The first stage is a linear program
formulated in terms of the joint state-action probabilities. The second stage
is a regularized problem formulated in terms of the conditional probabilities
of actions given states. The regularization uses techniques from
nearly-isotonic regression. While a variety of iterative method can be used in
the first formulation of the problem, we show in numerical simulations that, in
particular, the alternating method of multipliers (ADMM) can be significantly
accelerated using the regularization step.
