A Mean Field Approach for Optimization in Particles Systems and Applications

Nicolas Gast 1 Bruno Gaujal 1
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : This paper investigates the limit behavior of Markov Decision Processes (MDPs) made of independent particles evolving in a common environment, when the number of particles goes to infinity. In the finite horizon case or with a discounted cost and an infinite horizon, we show that when the number of particles becomes large, the optimal cost of the system converges almost surely to the optimal cost of a discrete deterministic system (the ``optimal mean field''). Convergence also holds for optimal policies. We further provide insights on the speed of convergence by proving several central limits theorems for the cost and the state of the Markov decision process with explicit formulas for the variance of the limit Gaussian laws. Then, our framework is applied to a brokering problem in grid computing. The optimal policy for the limit deterministic system is computed explicitly. Several simulations with growing numbers of processors are reported. They compare the performance of the optimal policy of the limit system used in the finite case with classical policies (such as Join the Shortest Queue) by measuring its asymptotic gain as well as the threshold above which it starts outperforming classical policies.
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00368011
Contributeur : Nicolas Gast <>
Soumis le : mercredi 10 juin 2009 - 16:39:30
Dernière modification le : jeudi 11 janvier 2018 - 06:21:39
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 17:27:36

Fichiers

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

Identifiants

  • HAL Id : inria-00368011, version 3
  • ARXIV : 0903.2352

Collections

Citation

Nicolas Gast, Bruno Gaujal. A Mean Field Approach for Optimization in Particles Systems and Applications. [Research Report] RR-6877, INRIA. 2009, pp.23. 〈inria-00368011v3〉

Partager

Métriques

Consultations de la notice

433

Téléchargements de fichiers

167