Planning by Prioritized Sweeping with Small Backups

Harm Van Seijen, Rich Sutton
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):361-369, 2013.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-vanseijen13, title = {Planning by Prioritized Sweeping with Small Backups}, author = {Van Seijen, Harm and Sutton, Rich}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {361--369}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/vanseijen13.pdf}, url = {https://proceedings.mlr.press/v28/vanseijen13.html}, abstract = {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. } }
Endnote
%0 Conference Paper %T Planning by Prioritized Sweeping with Small Backups %A Harm Van Seijen %A Rich Sutton %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-vanseijen13 %I PMLR %P 361--369 %U https://proceedings.mlr.press/v28/vanseijen13.html %V 28 %N 3 %X 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.
RIS
TY - CPAPER TI - Planning by Prioritized Sweeping with Small Backups AU - Harm Van Seijen AU - Rich Sutton BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-vanseijen13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 361 EP - 369 L1 - http://proceedings.mlr.press/v28/vanseijen13.pdf UR - https://proceedings.mlr.press/v28/vanseijen13.html AB - 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. ER -
APA
Van Seijen, H. & Sutton, R.. (2013). Planning by Prioritized Sweeping with Small Backups. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):361-369 Available from https://proceedings.mlr.press/v28/vanseijen13.html.

Related Material