Sur le principe d'optimalité de Bellman pour les zs-POSG - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (2) , (1, 2) , (3) , (1)
1
2
3

Abstract

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
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : hal-03081320 , version 1

Cite

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⟩
65 View
75 Download

Share

Gmail Facebook Twitter LinkedIn More