A Mean Field Approach for Optimization in Discrete Time

Nicolas Gast 1 Bruno Gaujal 2
2 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 made of independent objects evolving in a common environment, when the number of objects (N) goes to infinity. In the finite horizon case, we show that when the number of objects becomes large, the optimal cost of the system converges to the optimal cost of a discrete time system that is deterministic. Convergence also holds for optimal policies. We further provide bounds on the speed of convergence by proving second order results that resemble central limits theorems for the cost and the state of the Markov decision process, with explicit formulas for the limit. These bounds (of order 1/N−−√ ) are proven to be tight in a numerical example. One can even go further and get convergence of order logN−−−−√/N to a stochastic system made of the mean field limit and a Gaussian term. Our framework is applied to a brokering problem in grid computing. 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 by measuring its asymptotic gain. Several extensions are also discussed. In particular, for infinite horizon cases with discounted costs, we show that first order limits hold and that second order results also hold as long as the discount factor is small enough. As for infinite horizon cases with non-discounted costs, examples show that even the first order limits may not hold.
Type de document :
Article dans une revue
Journal of Discrete Event Dynamic Systems, Springer, 2011, 21, pp.63-101. 〈10.1007/s10626-010-0094-3〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788770
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 11:09:57
Dernière modification le : jeudi 11 janvier 2018 - 06:21:39

Identifiants

Collections

Citation

Nicolas Gast, Bruno Gaujal. A Mean Field Approach for Optimization in Discrete Time. Journal of Discrete Event Dynamic Systems, Springer, 2011, 21, pp.63-101. 〈10.1007/s10626-010-0094-3〉. 〈hal-00788770〉

Partager

Métriques

Consultations de la notice

199