Nonconvex Regularization for Markov Decision Processes: Modeling and Algorithms

This paper investigates efficient algorithm for Markov Decision Processes (MDPs) through Linear programming (LP). Generally, solving large-scale MDPs via standard LP solvers faces significant computational bottlenecks in matrix factorization. To tackle this problem, we introduced a novel sparse formulation for discounted MDPs using nonconvex regularization. Despite being combinatorial in nature, we show that the formulation can be solved efficiently by an alternating direction method of multipliers with linear convergence rate and a state-of-the-art performance.