Skip to Main content Skip to Navigation
New interface
Journal articles

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.
Complete list of metadata
Contributor : Arnaud Legrand Connect in order to contact the contributor
Submitted on : Friday, February 15, 2013 - 11:09:57 AM
Last modification on : Tuesday, August 2, 2022 - 4:24:53 AM

Links full text



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



Record views