Solving an Infinite-Horizon Discounted Markov Decision Process by DC Programming and DCA
Vinh Thanh Ho, Hoai An Le Thi · Advances in intelligent systems and computing · 2016
In this paper, we consider a decision problem modeled by Markov decision processes (written as MDPs). Solving a Markov decision problem amounts to searching for a policy, in a given set, which optimizes a performance criterion. In the considered MDP problem, we address the discounted criterion with the aim of characterizing the policies which provide the best sequence of rewards. In the literature, there are three main approaches applied to solve MDPs with a discounted criterion: linear programming, value iteration and policy iteration. In this paper, we are interested in the optimization approach to the discounted MDPs. Along this line, we describe an optimization model by studying the minimization of the different norms of Optimal Bellman Residual. In general, it can be formulated as a DC (Difference of Convex functions) program for which the unified DC programming and DCA (DC Algorithms) are applied. In our works, we propose a new optimization model and a suitable DC decomposition for the model of MDPs. Numerical experiments are performed on the stationary Garnet problems. The comparative results with the linear programming method for the discounted MDPs illustrate the efficiency of our proposed approach in terms of the quality of the obtained solutions.