Mean Field Markov Decision Processes

We consider mean-field control problems in discrete time with discounted reward, infinite time horizon and compact state and action space. The existence of optimal policies is shown and the limiting mean-field problem is derived when the number of individuals tends to infinity. Moreover, we consider the average reward problem and show that the optimal policy in this mean-field limit is e-optimal for the discounted problem if the number of individuals is large and the discount factor close to one. This result is very helpful, because it turns out that in the special case when the reward does only depend on the distribution of the individuals, we obtain a very interesting subclass of problems where an average reward optimal policy can be obtained by first computing an optimal measure from a static optimization problem and then achieving it with Markov Chain Monte Carlo methods. We give two applications: Avoiding congestion an a graph and optimal positioning on a market place which we solve explicitly.

Automated summary

This article investigates mean-field control problems in discrete time, including discounted reward, infinite time horizon, and compact state and action space. The existence of optimal policies is proven, and the limiting mean-field problem is derived as the number of individuals approaches infinity. Furthermore, the average reward problem is considered, and it is shown that the optimal policy in this mean-field limit is e-optimal for the discounted problem when the number of individuals is large and the discount factor is close to one. This result is significant for obtaining an average reward optimal policy in problems where the reward depends only on the distribution of individuals, by first computing an optimal measure from a static optimization problem and then achieving it with Markov Chain Monte Carlo methods. Two applications are provided: congestion avoidance on a graph and optimal positioning on a market place, which are explicitly solved.