Estimate and approximate policy iteration algorithm for discounted Markov decision models with bounded costs and Borel spaces

Article type: Research Article

Authors: Robles-Alcaráz, M. Teresa | Vega-Amaya, Óscar | Minjárez-Sosa, J. Adolfo^{; *}

Affiliations: Departamento de Matemáticas, Universidad de Sonora, Rosales s/n, Col. Centro, 83000 Hermosillo, Sonora, Mexico

Correspondence: [*] Corresponding author. E-mail: aminjare@mat.uson.mx.

Abstract: This paper provides finite-time performance bounds for the approximate policy iteration (API) algorithm in discounted Markov decision models. This is done for a class of approximation operators called averagers. An averager is a positive linear operator with norm equal to one with an additional continuity property. The class of averagers includes several of the usual interpolation schemes as lineal and multilinear approximations, kernel-based approximators among others. The API algorithm is studied under two settings. In the first one, the transition probability is completely known and the performance bounds are given in terms of the approximation errors and the stopping error of the policy iteration algorithm. In the second setting, the system evolution is given by a difference equation where the distribution of the random disturbance is unknown. Thus, in addition to the errors by the application of the API, in this case the performance bounds also depend on a statistical estimation error. The results are illustrated with numerical approximations for a class of inventory systems.

Keywords: Markov decision processes, discounted criterion, approximate policy iteration, density estimation

DOI: 10.3233/RDA-160116

Journal: Risk and Decision Analysis, vol. 6, no. 2, pp. 79-95, 2017