Symbolic Dynamic Programming for Discrete and Continuous State MDPs

Scott Sanner, Karina Valdivia Delgado, Leliane Nunes de Barros
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:714-723, 2011.

Abstract

Many real-world decision-theoretic planning problems can be naturally modeled with discrete and continuous state Markov decision processes (DC-MDPs). While previous work has addressed automated decision-theoretic planning for DCMDPs, optimal solutions have only been defined so far for limited settings, e.g., DC-MDPs having hyper-rectangular piecewise linear value functions. In this work, we extend symbolic dynamic programming (SDP) techniques to provide optimal solutions for a vastly expanded class of DCMDPs. To address the inherent combinatorial aspects of SDP, we introduce the XADD - a continuous variable extension of the algebraic decision diagram (ADD) - that maintains compact representations of the exact value function. Empirically, we demonstrate an implementation of SDP with XADDs on various DC-MDPs, showing the first optimal automated solutions to DCMDPs with linear and nonlinear piecewise partitioned value functions and showing the advantages of constraint-based pruning for XADDs.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-sanner11a, title = {Symbolic Dynamic Programming for Discrete and Continuous State MDPs}, author = {Sanner, Scott and Delgado, Karina Valdivia and de Barros, Leliane Nunes}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {714--723}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/sanner11a/sanner11a.pdf}, url = {https://proceedings.mlr.press/r9/sanner11a.html}, abstract = {Many real-world decision-theoretic planning problems can be naturally modeled with discrete and continuous state Markov decision processes (DC-MDPs). While previous work has addressed automated decision-theoretic planning for DCMDPs, optimal solutions have only been defined so far for limited settings, e.g., DC-MDPs having hyper-rectangular piecewise linear value functions. In this work, we extend symbolic dynamic programming (SDP) techniques to provide optimal solutions for a vastly expanded class of DCMDPs. To address the inherent combinatorial aspects of SDP, we introduce the XADD - a continuous variable extension of the algebraic decision diagram (ADD) - that maintains compact representations of the exact value function. Empirically, we demonstrate an implementation of SDP with XADDs on various DC-MDPs, showing the first optimal automated solutions to DCMDPs with linear and nonlinear piecewise partitioned value functions and showing the advantages of constraint-based pruning for XADDs.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Symbolic Dynamic Programming for Discrete and Continuous State MDPs %A Scott Sanner %A Karina Valdivia Delgado %A Leliane Nunes de Barros %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-sanner11a %I PMLR %P 714--723 %U https://proceedings.mlr.press/r9/sanner11a.html %V R9 %X Many real-world decision-theoretic planning problems can be naturally modeled with discrete and continuous state Markov decision processes (DC-MDPs). While previous work has addressed automated decision-theoretic planning for DCMDPs, optimal solutions have only been defined so far for limited settings, e.g., DC-MDPs having hyper-rectangular piecewise linear value functions. In this work, we extend symbolic dynamic programming (SDP) techniques to provide optimal solutions for a vastly expanded class of DCMDPs. To address the inherent combinatorial aspects of SDP, we introduce the XADD - a continuous variable extension of the algebraic decision diagram (ADD) - that maintains compact representations of the exact value function. Empirically, we demonstrate an implementation of SDP with XADDs on various DC-MDPs, showing the first optimal automated solutions to DCMDPs with linear and nonlinear piecewise partitioned value functions and showing the advantages of constraint-based pruning for XADDs. %Z Reissued by PMLR on 04 October 2026.
APA
Sanner, S., Delgado, K.V. & de Barros, L.N.. (2011). Symbolic Dynamic Programming for Discrete and Continuous State MDPs. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:714-723 Available from https://proceedings.mlr.press/r9/sanner11a.html. Reissued by PMLR on 04 October 2026.

Related Material