Reoptimization Nearly Solves Weakly Coupled Markov Decision Processes

We propose a new policy, called the LP-update policy, to solve finite horizon weakly-coupled Markov decision processes. The latter can be seen as multi-constraint multi-action bandits, and generalize the classical restless bandit problems. Our solution is based on re-solving periodically a relaxed version of the original problem, that can be cast as a linear program (LP). When the problem is made of N statistically identical sub-components, we show that the LP-update policy becomes asymptotically optimal at rate O(T2/√N). This rate can be improved to O(T/√N) if the problem satisfies some ergodicity property and to O(1/N) if the problem is non-degenerate. The definition of non-degeneracy extends the same notion for restless bandits. By using this property, we also improve the computational efficiency of the LP-update policy. We illustrate the performance of our policy on randomly generated examples, as well as a generalized applicant screening problem, and show that it outperforms existing heuristics.