Sur le principe d'optimalité de Bellman pour les zs-POSG - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Sur le principe d'optimalité de Bellman pour les zs-POSG

Résumé

Many non-trivial sequential decision-making problems are efficiently solved by relying on Bellman's optimality principle, i.e., exploiting the fact that sub-problems are nested recursively within the original problem. Here we show how it can apply to (infinite horizon) 2-player zero-sum partially observable stochastic games (zs-POSGs) by (i) taking a central planner's viewpoint, which can only reason on a sufficient statistic called occupancy state, and (ii) turning such problems into zero-sum occupancy Markov games (zs-OMGs). Then, exploiting the Lipschitz-continuity of the value function in occupancy space, one can derive a version of the HSVI algorithm (Heuristic Search Value Iteration) that provably finds an-Nash equilibrium in finite time.
De nombreux problèmes de prise de décision séquentielle sont résolus efficacement en exploitant le principe d'optimalité de Bellman, c'est-à-dire l'imbrication récursive de sous-problèmes dans le problème original. Nous montrons ici qu'il peut être appliqué aux jeux stochastiques partiellement observables à 2 joueurs et somme nulle (zs-POSG) en (i) prenant le point de vue d'un planificateur central, qui ne peut raisonner que sur une statistique suffisante appelée état d'occupation, et (ii) transformant de tels problèmes en des jeux de Markov dans l'espace des «états d'occupation» à somme nulle (zs-OMG). Ensuite, en exploitant des propriétés de Lipschitz-continuité de la fonction de valeur optimale, on peut dériver une version de l'algorithme HSVI (Heuristic Search Value Iteration) qui trouve un-équilibre de Nash en temps fini. Mots Clef POSG ; ; principe d'optimalité de Bellman ; Heuristic Search Value Iteration.
Fichier principal
Vignette du fichier
resume.pdf (157.34 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03081320 , version 1 (18-12-2020)

Identifiants

  • HAL Id : hal-03081320 , version 1

Citer

Olivier Buffet, Jilles Dibangoye, Aurélien Delage, Abdallah Saffidine, Vincent Thomas. Sur le principe d'optimalité de Bellman pour les zs-POSG. JFPDA 2020 - Journées Francophones surla Planification, la Décision et l’Apprentissagepour la conduite de systèmes, Jun 2020, Angers (virtuel), France. pp.1-3. ⟨hal-03081320⟩
117 Consultations
152 Téléchargements

Partager

Gmail Facebook X LinkedIn More