Journal article
A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs
European journal of operational research, Vol.258(1), pp.216-229
04/01/2017
DOI: 10.1016/j.ejor.2016.09.040
Abstract
•We make recent advances in rollout algorithms more accessible.•We formalize rollout variants exploiting the pre- and post-decision states.•We present new analytical results relating the performance of rollout variants.•Our policy-based proofs make a closer connection dynamic programming.•We apply our framework to a dynamic and stochastic knapsack problem.
Rollout algorithms have enjoyed success across a variety of domains as heuristic solution procedures for stochastic dynamic programs (SDPs). However, because most rollout implementations are closely tied to specific problems, the visibility of advances in rollout methods is limited, thereby making it difficult for researchers in other fields to extract general procedures and apply them to different areas. We present a rollout algorithm framework to make recent advances in rollout methods more accessible to researchers seeking heuristic policies for large-scale, finite-horizon SDPs. We formalize rollout variants exploiting the pre- and post-decision state variables as a means of overcoming computational limitations imposed by large state and action spaces. We present a unified analytical discussion, generalizing results from the literature and introducing new results that relate the performance of the rollout variants to one another. Relative to the literature, our policy-based approach to presenting and proving results makes a closer connection to the underpinnings of dynamic programming. Finally, we illustrate our framework and analytical results via application to a dynamic and stochastic multi-compartment knapsack problem.
Details
- Title: Subtitle
- A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs
- Creators
- Justin C. Goodson - Saint Louis UniversityBarrett W. Thomas - University of IowaJeffrey W. Ohlmann - University of Iowa
- Resource Type
- Journal article
- Publication Details
- European journal of operational research, Vol.258(1), pp.216-229
- Publisher
- Elsevier B.V
- DOI
- 10.1016/j.ejor.2016.09.040
- ISSN
- 0377-2217
- eISSN
- 1872-6860
- Language
- English
- Date published
- 04/01/2017
- Academic Unit
- Bus Admin College; Business Analytics
- Record Identifier
- 9984380376102771
Metrics
3 Record Views