Computing monotone policies for Markov decision processes: a nearly-isotonic penalty approach
For researchers working on MDPs with monotone policies, this method offers a way to speed up optimization, though the improvement is incremental.
This paper proposes a two-stage alternating convex optimization scheme for solving MDPs with monotone optimal policies, using nearly-isotonic regularization to accelerate ADMM. Numerical simulations show significant acceleration compared to standard ADMM.
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.