State-Independent Control for Constrained Markov Decision Processes With Birth-Death Dynamics

In many applications, we regularly face the fundamental problem of allocating a common resource (funding, time, energy, etc.) among a network of processes that evolve in a continuous-space according to a birth-death dynamics. The state of each process tends to gradually improve with the resource and gradually degrade without it. Formulated as a Constrained Markov Decision Process (CMDP), the problem is typically attacked in the continuous space directly using the function approximation method or in discrete space with a fixed granularity. In this work, we investigated an alternative method based on the fact that the granularity of discretization has a crucial impact on the size and the evolution of the state-space. Increasing the granularity has the desirable effect of increasing the control of the processes (due to increased interaction regularity), but it also comes with the burden of an increasing state-space. Without function approximation, it is well-known that finding the optimal solution of CMDP is formidably difficult as the state-space grows. We have taken a fresh look at designing State-Independent policies whose complexity does not scale with the discretization granularity parameter <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> of the underlying continuous space processes. In particular, for a constrained-resource allocation problem over birth-death type processes, we developed state-independent policies that guarantee asymptotic-optimality as the discretization granularity <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> grows. We also show, through numerical comparisons, that our design has a lower running time compared to alternative designs including index-based methods and function approximation methods.