A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs

作     者：Goodson, Justin C. Thomas, Barrett W. Ohlmann, Jeffrey W. 

作者机构：St Louis Univ John Cook Sch Business Dept Operat & Informat Technol Management 3674 Lindell Blvd St Louis MO 63108 USA Univ Iowa Tippie Coll Business Dept Management Sci Iowa City IA 52242 USA 

出 版 物：《EUROPEAN JOURNAL OF OPERATIONAL RESEARCH》 (欧洲运筹学杂志)

年 卷 期：2017年第258卷第1期

页      面：216-229页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Dynamic programming Rollout algorithm Stochastic dynamic programming Approximate dynamic programming 

摘      要：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. (C) 2016 Published by Elsevier B.V.