Structural approximations in discounted semi-Markov games

Eugenio Della Vecchia; Silvia C. Di Marco; Alain Jean-Marie

hal-00764217, version 1

Structural approximations in discounted semi-Markov games

Eugenio Della Vecchia^a^, 1, Silvia C. Di Marco^a^, 1, Alain Jean-Marie ()^b^, 2, 3

N° RR-8162 (2012)

Résumé : We consider the problem of approximating the values and the equilibria in two-person zero-sum discounted semi-Markov games with infinite horizon and compact action spaces, when several uncertainties are present about the parameters of the model. Specifically: on the one hand, we study approximations made on the transition probabilities, the discount factor and the reward functions when the state space is a borelian set. On the other hand, we study approximations on the state space for denumerable ones. Our results are based on those of Tidball and Altman (SIAM J. Control and Optimization, 1996) on generic zero-sum games. We provide conditions under which these results can be applied. We also discuss the application of such approximations for finite-horizon games, in relation with the Approximate Rolling Horizon procedure proposed in Della Vecchia et al. (INRIA RR 8019, 2012).

a – Universidad Nacional de Rosario - CONICET
b – INRIA - LIRMM
1 : Facultad de Ciencias Exactas, Ingenieria y Agrimensura [Santa Fe] (FCEIA)
UNR
2 : Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
CNRS : UMR5506 – Université Montpellier II - Sciences et techniques
3 : MAESTRO (INRIA Sophia Antipolis)
INRIA – Université Montpellier II - Sciences et techniques

hal-00764217, version 1
http://hal.inria.fr/hal-00764217
oai:hal.inria.fr:hal-00764217
Contributeur : Alain Jean-Marie <>
Soumis le : Mercredi 12 Décembre 2012, 15:45:56
Dernière modification le : Mercredi 12 Décembre 2012, 16:05:25

Voir la fiche détaillée

Documents associés

PDF :

Exporter

Bibtex EndNote TEI RefWorks

%F hal-00764217, version 1
%0 Report
%U http://hal.inria.fr/hal-00764217
%2 MATH:MATH_OC
%T Structural approximations in discounted semi-Markov games
%A Della Vecchia, Eugenio
%A Di Marco, Silvia C.
%A Jean-Marie, Alain
%+ Facultad de Ciencias Exactas, Ingenieria y Agrimensura [Santa Fe] - FCEIA , Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM , MAESTRO - INRIA Sophia Antipolis
%X We consider the problem of approximating the values and the equilibria in two-person zero-sum discounted semi-Markov games with infinite horizon and compact action spaces, when several uncertainties are present about the parameters of the model. Specifically: on the one hand, we study approximations made on the transition probabilities, the discount factor and the reward functions when the state space is a borelian set. On the other hand, we study approximations on the state space for denumerable ones. Our results are based on those of Tidball and Altman (SIAM J. Control and Optimization, 1996) on generic zero-sum games. We provide conditions under which these results can be applied. We also discuss the application of such approximations for finite-horizon games, in relation with the Approximate Rolling Horizon procedure proposed in Della Vecchia et al. (INRIA RR 8019, 2012).
%2 Nous considérons le problème de l'approximation des valeurs et des équilibres d'un jeu semi-Markovien actualisé, en horizon infi ni avec des ensembles d'actions compacts, en présence d'incertitude sur plusieurs paramètres du modèle. Spécifi quement: d'une part nous étudions les approximations sur les probabilités de transition, sur le facteur d'actualisation et sur les coûts, quand l'espace d'états est un ensemble Borélien. D'autre part, nous étudions les approximations de l'ensemble d'états quand celui-ci est dénombrable. Nos résultats sont basés sur ceux de (SIAM J. Control and Optimization, 1996). Nous donnons des conditions sous lesquelles ces résultats peuvent être appliqués. Nous discutons aussi de l'application de telles approximations à des jeux en horizon fini, en relation avec la procédure de l'horizon roulant approchée, proposée dans Della Vecchia et al. (INRIA RR 8019, 2012).
%G Anglais
%2 Rapport de recherche
%P 19
%8 2012-12-12
%K Game theory, Semi-Markov games, Zero-sum games
%Z RR-8162

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="hal-00764217"><monogr>
<author><persName><forename>Eugenio</forename><surname>Della Vecchia</surname></persName>
<affiliation>
<orgName type="laboratory">FCEIA</orgName>
<orgName type="team">Facultad de Ciencias Exactas, Ingenieria y Agrimensura [Santa Fe]</orgName>
<country>AR</country>
<orgName type="institution">UNR</orgName>
</affiliation>
</author>
<author><persName><forename>Silvia C.</forename><surname>Di Marco</surname></persName>
<affiliation>
<orgName type="laboratory">FCEIA</orgName>
<orgName type="team">Facultad de Ciencias Exactas, Ingenieria y Agrimensura [Santa Fe]</orgName>
<country>AR</country>
<orgName type="institution">UNR</orgName>
</affiliation>
</author>
<author><persName><forename>Alain</forename><surname>Jean-Marie</surname></persName>
<affiliation>
<orgName type="laboratory">LIRMM</orgName>
<orgName type="team">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5506</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">MAESTRO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<title type="main" level="m">Structural approximations in discounted semi-Markov games</title><title type="main" level="m">Structural approximations in discounted semi-Markov games</title><imprint><biblScope type="publicationDate">2012-12-12</biblScope><biblScope type="pp">19</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00764217</idno><idno type="HALFile">http://hal.inria.fr/hal-00764217/PDF/RR-8162.pdf</idno></biblStruct>
</listBibl>
</listBibl>