HSVI pour zs-POSG usant de propriétés de convexité, concavité, et Lipschitz-continuité
Résumé
Solving a 2-player zero-sum partially observable stochastic game (zs-POSG) typically relies on turning it into an extensive-form game, thus losing structural information contained in the original representation. We prevent such a loss by turning the problem instead into an occupancy Markov game, which allows building on state-of-the-art approaches for partially observable Markov decision processes, decentralized POMDPs, and a number of subclasses of zs-POSGs. To apply Bellman’s optimality principle in this setting, we (i) exhibit novel continuity properties of the optimal value function ; (ii) derive point-based bounding approximators ; and (iii) propose efficient backup operators based on linear programming. A variant of SMITH et SIMMONS’s (2005) HSVI algorithm is built on these ideas and we prove its finite-time convergence to an -optimal solution before presenting experimental results.
La résolution d'un jeu stochastique partiellement observable à 2 joueurs et somme nulle (zs-POSG) repose typiquement sur sa transformation en un jeu en forme extensive, perdant ainsi de l'information structurelle contenue dans la représentation originale. Nous évitons une telle perte en transformant le problème plutôt en un jeu de Markov sur les états d'occupation, ce qui permet de tirer parti d'approches de l'état de l'art pour les processus de décision markoviens partiellement observables, les POMDP décentralisés, et un certain nombre de sous-classes de zs-POSG. Pour appliquer le principe d'optimalité de Bellman dans ce cadre, nous (i) exhibons des propriétés de continuité originales de la fonction de valeur optimale ; (ii) dérivons des approximateurs encadrants à base de points ; et (iii) proposons des opérateurs de mise à jour efficaces reposant sur la programmation linéaire. Une variante de l'algorithm HSVI de SMITH et SIMMONS [23] est construite sur la base de ces idées et nous prouvons sa convergence vers une solution-optimale avant de présenter des résultats expérimentaux.
Origine : Fichiers produits par l'(les) auteur(s)