Solving very large weakly coupled Markov decision processes

TLDR

These problems consist of many independent tasks modeled as separate MDPs, but the tasks are weakly coupled through shared resource constraints that limit actions across tasks. The authors propose a method to compute approximately optimal solutions for stochastic resource allocation problems represented as MDPs. The method exploits task independence and resource constraints to avoid full state enumeration, using heuristic techniques that combine individual MDP solutions into an approximate global policy. The technique successfully solves problems with thousands of tasks, yielding approximate solutions that standard methods cannot handle.

Abstract

We present a technique for computing approximately optimal solutions to stochastic resource allocation problems modeled as Markov decision processes (MDPS). We exploit two key properties to avoid explicitly enumerating the very large state and action spaces associated with these problems. Fist, the problems are composed of multiple tasks whose utilities are independent. Second, the actions taken with respect to (or resources allocated to) a task do not influence the status of any other task. We can therefore view each task as an MDP. However these MDPS are weakly coupled by resource constraints: actions selected for one MDP restrict the actions available to others. We describe heuristic techniques for dealing with several classes of constraints that use the solutions for individual MDPS to construct an approximate global solution. We demonstrate this technique on problems involving thousands of tasks, approximating the solution to problems that are far beyond the reach of standard methods.