Rollout Algorithms for Stochastic Scheduling Problems

By Dimitri P. Bertsekas, David A. Castañón. 1998

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings (2021, neutral): “One closely related approach is the Rollout algorithm (Bertsekas & Castanon, 1999), which given an initial policy, computes Monte Carlo rollouts of the belief-space MDP assuming that this policy is played going forward, and plays the action with the highest expected value.”
Variance Reduction in Monte-Carlo Tree Search (2011, methodology): “Under some mild assumptions, this technique is provably superior to executing the default policy [3].”
Optimization under uncertainty: state-of-the-art and opportunities (2004, unknown): “…et al., 2003; Sernland, Olsson, & Holmgren, 2003; Yalcin & Stott, 2000); • production planning (Cheng, Subrahmanian, & Westerberg, 2003), scheduling (Bertsekas & Castañon, 1999; Mo, Gjelsvik, & Grundt, 2001; Shen & Leachman, 2003), and supply chain management (Bitran, Caldentey, &…”
Potential-based reward shaping for finite horizon online POMDP planning (2016, methodology): “, Rollout [3], POMCP [19], DESPOT [21]), also called Monte Carlo Tree Search (MCTS) when used with tree-based policy representations, perform sparse random sampling of future belief states to estimate cumulative, future rewards.”
Learning Algorithms for Markov Decision Processes with Average Cost (2001, background): “A good choice of basis functions is crucial, and it has been suggested that they be based upon sample simulation runs [6].”
Dynamic Programming and Suboptimal Control: A Survey from ADP to MPC (2005, methodology): “For further work on rollout algorithms, see Christodouleas [Chr97], Bertsekas [12], Bertsekas and Castanon [4], Secomandi [43–45], Bertsimas and Demir [5], Ferris and Voelker [23,24], McGovern et al.”
Online Planning Algorithms for POMDPs (2008, methodology): “…approaches (Satia & Lave, 1973; Washington, 1997; Barto, Bradtke, & Singhe, 1995; Paquet, Tobin, & Chaib-draa, 2005; McAllester & Singh, 1999; Bertsekas & Castanon, 1999; Shani, Brafman, & Shimony, 2005) try to circumvent the complexity of computing a policy by planning online only for the…”
DESPOT: Online POMDP Planning with Regularization (2013, methodology): “…and can be combined, by using approximate or partial policies computed ofﬂine as the default policies at the leaves of the search tree for online planning (Bertsekas & Castanon, 1999; Gelly & Silver, 2007), or as macro-actions to shorten the search horizon (He, Brunskill, & Roy, 2011).”
Monte-Carlo Planning in Large POMDPs (2010, background): “Monte-Carlo planning is a very different paradigm for online planning in POMDPs [2, 7].”