Using linear programming duality for solving finite horizon Dec-POMDPs

Raghav Aras 1 Alain Dutech 1 François Charpillet 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper studies the problem of finding an optimal finite horizon joint policy for a decentralized partially observable Markov decision process (Dec-POMDP). We present a new algorithm for finding an optimal joint policy. The algorithm is based on the fact that the necessary condition for a joint policy to be optimal is that it be locally optimal (that is, a Nash equilibrium). Through the application of linear programming duality, the necessary condition can be transformed to a nonlinear program which can then further be transformed to a 0-1 mixed integer linear program (MILP) whose optimal solution is an optimal joint policy (in the sequence form). The proposed algorithm thus consists of solving this 0-1 MILP. Computational experience of the 0-1 MILP on two and three agent DEC-POMDPs gives mixed results. On some problems it is faster than existing algorithms, on others it is slower.
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00320645
Contributeur : Raghav Aras <>
Soumis le : mardi 16 septembre 2008 - 14:49:56
Dernière modification le : jeudi 11 janvier 2018 - 06:19:50
Document(s) archivé(s) le : mardi 28 juin 2011 - 16:35:05

Fichiers

RR-6641.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00320645, version 1

Collections

Citation

Raghav Aras, Alain Dutech, François Charpillet. Using linear programming duality for solving finite horizon Dec-POMDPs. [Technical Report] RR-6641, INRIA. 2008, pp.27. 〈inria-00320645〉

Partager

Métriques

Consultations de la notice

389

Téléchargements de fichiers

184