4th International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

A Mean Field Approach for Optimization in Particle Systems and Applications

Download558 downloads
  • @INPROCEEDINGS{10.4108/ICST.VALUETOOLS2009.7477,
        author={Nicolas Gast and Bruno Gaujal},
        title={A Mean Field Approach for Optimization in Particle Systems and Applications},
        proceedings={4th International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ICST},
        proceedings_a={VALUETOOLS},
        year={2010},
        month={5},
        keywords={Mean Field Markov Decision Process Brokering.},
        doi={10.4108/ICST.VALUETOOLS2009.7477}
    }
    
  • Nicolas Gast
    Bruno Gaujal
    Year: 2010
    A Mean Field Approach for Optimization in Particle Systems and Applications
    VALUETOOLS
    ICST
    DOI: 10.4108/ICST.VALUETOOLS2009.7477
Nicolas Gast1,*, Bruno Gaujal2,*
  • 1: Université Joseph Fourier and LIG, 51, avenue Jean Kuntzmann, Montbonnont, France.
  • 2: NRIA and LIG, 51, avenue Jean Kuntzmann, Montbonnont, France.
*Contact email: nicolas.gast@imag.fr, bruno.gaujal@inria.fr

Abstract

This paper investigates the limit behavior of Markov decision processes made of independent particles evolving in a common environment, when the number of particles goes to infnity. In the fnite horizon case or with a discounted cost and an infnite horizon, we show that when the number of particles becomes large, the optimal cost of the system converges to the optimal cost of a deterministic system. 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 limit. Then, 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 fnite case with classical policies by measuring its asymptotic gain.