Rollout algorithms provide a method for approximately solving a large class of discrete and dynamic optimization problems. Using a lookahead approach, rollout algorithms leverage repeated use of a greedy algorithm, or base policy, to intelligently make decisions. This technique is easy to implement, inherits performance bounds given by the selected base policy, and performs very well in practice. In some cases the observed performance is near optimal. However, there have been few theoretical results guaranteeing a strict improvement over base policies.
