A distance for probability spaces, and long-term values in Markov Decision Processes and Repeated Games

Given a finite set $K$, we denote by $X=\Delta(K)$ the set of probabilities on $K$ and by $Z=\Delta_f(X)$ the set of Borel probabilities on $X$ with finite support. Studying a Markov Decision Process with partial information on $K$ naturally leads to a Markov Decision Process with full information on $X$. We introduce a new metric $d_$ on $Z$ such that the transitions become $1$-Lipschitz from $(X, \|.\|1)$ to $(Z,d)$. In the first part of the article, we define and prove several properties of the metric $d_$. Especially, $d_$ satisfies a Kantorovich-Rubinstein type duality formula and can be characterized by using disintegrations. In the second part, we characterize the limit values in several classes of ''compact non expansive" Markov Decision Processes. In particular we use the metric $d_$ to characterize the limit value in Partial Observation MDP with finitely many states and in Repeated Games with an informed controller with finite sets of states and actions. Moreover in each case we can prove the existence of a generalized notion of uniform value where we consider not only the Cesàro mean when the number of stages is large enough but any evaluation function $\theta \in \Delta(\N^)$ when the impatience $I(\theta)=\sum_{t\geq 1} |\theta_{t+1}-\theta_t|$ is small enough.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00674998
Author Renault, Jérôme, Venel, Xavier
Maintainer CCSD
Last Updated May 26, 2026, 11:34 (UTC)
Created May 26, 2026, 11:34 (UTC)
Identifier hal-00674998
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Groupe de recherche en économie mathématique et quantitative (GREMAQ) ; Université Toulouse Capitole (UT Capitole) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Institut National de la Recherche Agronomique (INRA)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)
creator Renault, Jérôme
date 2012-02-28T00:00:00
harvest_object_id 506cc0ff-597d-4c39-9371-2ee5582fe9d9
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-09-23T00:00:00
relation https://hal.science/hal-01396680v1
set_spec type:UNDEFINED