caa a22 4500 445822643 CHVBK 20180317145248.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s10626-010-0094-3 doi (NATIONALLICENCE)springer-10.1007/s10626-010-0094-3 A mean field approach for optimization in discrete time [Elektronische Daten] [Nicolas Gast, Bruno Gaujal] 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/\sqrt{N}$) are proven to be tight in a numerical example. One can even go further and get convergence of order $\sqrt{\log N}/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. Springer Science+Business Media, LLC, 2010 Mean field nationallicence Markov decision process nationallicence Brokering nationallicence Gast Nicolas Grenoble Université, Grenoble, France aut Gaujal Bruno LIG, 51 av Jean Kuntzman, 38330, Montbonnot, France aut Discrete Event Dynamic Systems Springer US; http://www.springer-ny.com 21/1(2011-03-01), 63-101 0924-6703 21:1<63 2011 21 10626 https://doi.org/10.1007/s10626-010-0094-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10626-010-0094-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Gast Nicolas Grenoble Université, Grenoble, France aut NATIONALLICENCE 700 1- Gaujal Bruno LIG, 51 av Jean Kuntzman, 38330, Montbonnot, France aut NATIONALLICENCE 773 0- Discrete Event Dynamic Systems Springer US; http://www.springer-ny.com 21/1(2011-03-01), 63-101 0924-6703 21:1<63 2011 21 10626 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer