Long-Term Values in Markov Decision Processes and Repeated Games, and a New Distance for Probability Spaces.

Résumé Nous étudions les processus de décision de Markov à long terme et les maisons de jeu, avec des applications à tout PDM à observation partielle avec un nombre fini d'états et aux jeux répétés à somme nulle avec un contrôleur informé. Nous considérons un décideur qui maximise la somme pondérée t≥1 θtrt, où rt est la récompense attendue de la t-ième étape. Nous prouvons l'existence d'une notion très forte de valeur à long terme appelée valeur uniforme générale, représentant le fait que le décideur peut bien jouer indépendamment des évaluations (θt) t≥1 sur les étapes, à condition que la variation (ou impatience) totale t≥1 |θt+1 - θt| soit suffisamment petite. Ce résultat généralise les résultats précédents de Rosenberg, Solan et Vieille [35] et Renault [31] qui se concentrent sur les moyennes arithmétiques et les évaluations actualisées. De plus, nous donnons une caractérisation variationnelle de la valeur uniforme générale via l'introduction de mesures invariantes appropriées pour les problèmes de décision, généralisant le théorème fondamental des jeux de hasard ou la formule cavu d'Aumann-Maschler pour les jeux répétés à information incomplète. Outre l'introduction de mesures invariantes appropriées, la principale innovation dans nos preuves est l'introduction d'une nouvelle métrique d * telle que les MDP à observation partielle et les jeux répétés avec un contrôleur informé peuvent être associés à des problèmes auxiliaires qui sont non-expansifs par rapport à d *. Étant donné deux probabilités de Borel sur un sous-ensemble compact X d'un espace vectoriel normé, on définit d * (u, v) = sup f ∈D 1 |u(f) - v(f)|, où D1 est l'ensemble des fonctions satisfaisant : ∀x, y ∈ X, ∀a, b ≥ 0, af (x) - bf (y) ≤ ax - by. Le cas particulier où X est un simplexe doté de la norme L 1 est particulièrement intéressant : d * est la plus grande distance sur les probabilités à support fini sur X qui rend toute désintégration non-expansive. De plus, nous obtenons une formule de dualité de type Kantorovich-Rubinstein pour d * (u, v) impliquant des couples de mesures (α, β) sur X × X tels que la première marginale de α est u et la seconde marginale de β est v. Classification MSC : Primaire : 90C40 . Secondaire : 60J20, 91A15.