Accession Number:

AD1034909

Title:

A Comparison of Monte Carlo Tree Search and Rolling Horizon Optimization for Large Scale Dynamic Resource Allocation Problems

Descriptive Note:

Journal Article

Corporate Author:

MIT Lincoln Laboratory Lexington United States

Report Date:

2015-05-01

Pagination or Media Count:

46.0

Abstract:

Dynamic resource allocation DRA problems constitute an important class of dynamic stochastic optimization problems that arise in a variety of important real-world applications. DRA problems are notoriously difficult to solve to optimality since they frequently combine stochastic elements with intractably large state and action spaces. Although the artificial intelligence and operations research communities have independently proposed two successful frameworks for solving dynamic stochastic optimization problems Monte Carlo tree search MCTS and rolling horizon optimization RHO, respectively the relative merits of these two approaches are not well understood. In this paper, we adapt both MCTS and RHO to two problems a problem inspired by tactical wildlife management and a classical problem involving the control of queueing networks and undertake an extensive computational study comparing the two methods on large scale instances of both problems in terms of both the state and the action spaces. We show that both methods are able to greatly improve on a baseline, problem-specific heuristic. On smaller instances, the MCTS and RHO approaches perform comparably, but the RHO approach outperforms MCTS as the size of the problem increases for a fixed computational budget.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE