Optimally Controlling a Random Population

The population control problem is a parameterised problem where a controller sends messages to a whole population of identical finite-state agents, aiming to eventually move them all into a target state. The decision problem asks whether this can be achieved for arbitrarily large finite populations. We focus on the randomised version of this problem, where every agent is a copy of the same finite Markov Decision Process and non-determinism in the global action chosen by the controller is resolved independently and uniformly at random. Colcombet, Fijalkow and Ohlmann [Thomas Colcombet et al., 2021] showed that this problem is decidable, but without any complexity upper bound. We show that the random population control problem is in fact ExpTime-complete.