Adaptive Sampling Based Large-Scale Stochastic Resource Control∗

We consider closed-loop solutions to stochastic opti-mization problems of resource allocation type. They concern with the dynamic allocation of reusable re-sources over time to non-preemtive interconnected tasks with stochastic durations. The aim is to minimize the expected value of a regular performance measure. First, we formulate the problem as a stochastic shortest path problem and argue that our formulation has favorable properties, e.g., it has finite horizon, it is acyclic, thus, all policies are proper, and moreover, the space of con-trol policies can be safely restricted. Then, we propose an iterative solution. Essentially, we apply a reinforce-ment learning based adaptive sampler to compute a sub-optimal control policy. We suggest several approaches to enhance this solution and make it applicable to large-scale problems. The main improvements are: (1) the value function is maintained by feature-based support vector regression; (2) the initial exploration is guided by rollout algorithms; (3) the state space is partitioned by clustering the tasks while keeping the precedence con-straints satisfied; (4) the action space is decomposed and, consequently, the number of available actions in a state is decreased; and, finally, (5) we argue that the sampling can be effectively distributed among several processors. The effectiveness of the approach is demon-strated by experimental results on both artificial (bench-mark) and real-world (industry related) data