A perturbation approach to approximate value iteration for average cost Markov decision processes with borel spaces and bounded costs

Óscar Vega-Amaya, Joaquín López-Borbón

Research output: Contribution to journalArticle

Abstract

The present paper studies the approximate value iteration (AVI) algorithm for the average cost criterion with bounded costs and Borel spaces. It is shown the convergence of the algorithm and provided a performance bound assuming that the model satisfies a standard continuity-compactness assumption and a uniform ergodicity condition. This is done for the class of approximation procedures that can be represented by linear positive operators which give exact representation of constant functions and also satisfy certain continuity property. The main point is that these operators define transition probabilities on the state space of the controlled system. This has the following important consequences: (a) the approximating function is the average value of the target function with respect to the induced transition probability; (b) the approximation step in the AVI algorithm can be seen as a perturbation of the original Markov model; (c) the perturbed model inherits the ergodicity properties imposed on the original Markov model. These facts allow to bound the AVI algorithm performance in terms of the accuracy of the approximations given by this kind of operators for the primitive data model, namely, the one-step reward function and the system transition law. The bounds are given in terms of the supremum norm of bounded functions and the total variation norm of finite-signed measures. The results are illustrated with numerical approximations for a class of single item inventory systems with linear order cost, no set-up cost and no back-orders.

Original languageEnglish
Pages (from-to)81-113
Number of pages33
JournalKybernetika
Volume55
Issue number1
DOIs
StatePublished - 1 Jan 2019

Fingerprint

Value Iteration
Average Cost
Markov Decision Process
Perturbation
Costs
Transition Probability
Markov Model
Approximation
Uniform Ergodicity
Total Variation Norm
Linear Positive Operators
Mathematical operators
Signed Measure
Backorder
Setup Cost
Performance Bounds
Constant function
Inventory Systems
Transition Systems
Linear Order

Keywords

  • Approximate value iteration algorithm
  • Average cost criterion
  • Contraction
  • Markov decision processes
  • Non-expansive operators
  • Perturbed Markov decision models

Cite this

@article{4e00748b77f545de9836ae02c2e3076a,
title = "A perturbation approach to approximate value iteration for average cost Markov decision processes with borel spaces and bounded costs",
abstract = "The present paper studies the approximate value iteration (AVI) algorithm for the average cost criterion with bounded costs and Borel spaces. It is shown the convergence of the algorithm and provided a performance bound assuming that the model satisfies a standard continuity-compactness assumption and a uniform ergodicity condition. This is done for the class of approximation procedures that can be represented by linear positive operators which give exact representation of constant functions and also satisfy certain continuity property. The main point is that these operators define transition probabilities on the state space of the controlled system. This has the following important consequences: (a) the approximating function is the average value of the target function with respect to the induced transition probability; (b) the approximation step in the AVI algorithm can be seen as a perturbation of the original Markov model; (c) the perturbed model inherits the ergodicity properties imposed on the original Markov model. These facts allow to bound the AVI algorithm performance in terms of the accuracy of the approximations given by this kind of operators for the primitive data model, namely, the one-step reward function and the system transition law. The bounds are given in terms of the supremum norm of bounded functions and the total variation norm of finite-signed measures. The results are illustrated with numerical approximations for a class of single item inventory systems with linear order cost, no set-up cost and no back-orders.",
keywords = "Approximate value iteration algorithm, Average cost criterion, Contraction, Markov decision processes, Non-expansive operators, Perturbed Markov decision models",
author = "{\'O}scar Vega-Amaya and Joaqu{\'i}n L{\'o}pez-Borb{\'o}n",
year = "2019",
month = "1",
day = "1",
doi = "10.14736/kyb-2019-1-0081",
language = "Ingl{\'e}s",
volume = "55",
pages = "81--113",
journal = "Kybernetika",
issn = "0023-5954",
publisher = "Academy of Sciences of the Czech Republic",
number = "1",

}

A perturbation approach to approximate value iteration for average cost Markov decision processes with borel spaces and bounded costs. / Vega-Amaya, Óscar; López-Borbón, Joaquín.

In: Kybernetika, Vol. 55, No. 1, 01.01.2019, p. 81-113.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A perturbation approach to approximate value iteration for average cost Markov decision processes with borel spaces and bounded costs

AU - Vega-Amaya, Óscar

AU - López-Borbón, Joaquín

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The present paper studies the approximate value iteration (AVI) algorithm for the average cost criterion with bounded costs and Borel spaces. It is shown the convergence of the algorithm and provided a performance bound assuming that the model satisfies a standard continuity-compactness assumption and a uniform ergodicity condition. This is done for the class of approximation procedures that can be represented by linear positive operators which give exact representation of constant functions and also satisfy certain continuity property. The main point is that these operators define transition probabilities on the state space of the controlled system. This has the following important consequences: (a) the approximating function is the average value of the target function with respect to the induced transition probability; (b) the approximation step in the AVI algorithm can be seen as a perturbation of the original Markov model; (c) the perturbed model inherits the ergodicity properties imposed on the original Markov model. These facts allow to bound the AVI algorithm performance in terms of the accuracy of the approximations given by this kind of operators for the primitive data model, namely, the one-step reward function and the system transition law. The bounds are given in terms of the supremum norm of bounded functions and the total variation norm of finite-signed measures. The results are illustrated with numerical approximations for a class of single item inventory systems with linear order cost, no set-up cost and no back-orders.

AB - The present paper studies the approximate value iteration (AVI) algorithm for the average cost criterion with bounded costs and Borel spaces. It is shown the convergence of the algorithm and provided a performance bound assuming that the model satisfies a standard continuity-compactness assumption and a uniform ergodicity condition. This is done for the class of approximation procedures that can be represented by linear positive operators which give exact representation of constant functions and also satisfy certain continuity property. The main point is that these operators define transition probabilities on the state space of the controlled system. This has the following important consequences: (a) the approximating function is the average value of the target function with respect to the induced transition probability; (b) the approximation step in the AVI algorithm can be seen as a perturbation of the original Markov model; (c) the perturbed model inherits the ergodicity properties imposed on the original Markov model. These facts allow to bound the AVI algorithm performance in terms of the accuracy of the approximations given by this kind of operators for the primitive data model, namely, the one-step reward function and the system transition law. The bounds are given in terms of the supremum norm of bounded functions and the total variation norm of finite-signed measures. The results are illustrated with numerical approximations for a class of single item inventory systems with linear order cost, no set-up cost and no back-orders.

KW - Approximate value iteration algorithm

KW - Average cost criterion

KW - Contraction

KW - Markov decision processes

KW - Non-expansive operators

KW - Perturbed Markov decision models

UR - http://www.scopus.com/inward/record.url?scp=85064209372&partnerID=8YFLogxK

U2 - 10.14736/kyb-2019-1-0081

DO - 10.14736/kyb-2019-1-0081

M3 - Artículo

AN - SCOPUS:85064209372

VL - 55

SP - 81

EP - 113

JO - Kybernetika

JF - Kybernetika

SN - 0023-5954

IS - 1

ER -