A Comparison of Monte Carlo Tree Search and Rolling Horizon Optimization for Large Scale Dynamic Resource Allocation Problems
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 2015
- Accession Number
- AD1034909
Entities
People
- Dimitris Bertsimas
- John D. Griffith
- Mykel Kochenderfer
- Robert Moss
- Velibor V. Misic
- Vishal Gupta
Organizations
- MIT Lincoln Laboratory