  Efficient planning plays a crucial role in model-based reinforcement
learning. Traditionally, the main planning operation is a full backup based on
the current estimates of the successor states. Consequently, its computation
time is proportional to the number of successor states. In this paper, we
introduce a new planning backup that uses only the current value of a single
successor state and has a computation time independent of the number of
successor states. This new backup, which we call a small backup, opens the door
to a new class of model-based reinforcement learning methods that exhibit much
finer control over their planning process than traditional methods. We
empirically demonstrate that this increased flexibility allows for more
efficient planning by showing that an implementation of prioritized sweeping
based on small backups achieves a substantial performance improvement over
classical implementations.
