Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs

Luis Gustavo Vianna, Scott Sanner, Leliane de Barros
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:232-241, 2013.

Abstract

Recent advances in symbolic dynamic pro- gramming (SDP) combined with the ex- tended algebraic decision diagram (XADD) data structure have provided exact solutions for mixed discrete and continuous (hybrid) MDPs with piecewise linear dynamics and continuous actions. Since XADD-based ex- act solutions may grow intractably large for many problems, we propose a bounded er- ror compression technique for XADDs that involves the solution of a constrained bilin- ear saddle point problem. Fortuitously, we show that given the special structure of this problem, it can be expressed as a bilevel lin- ear programming problem and solved to op- timality in finite time via constraint gener- ation, despite having an infinite set of con- straints. This solution permits the use of efficient linear program solvers for XADD compression and enables a novel class of bounded approximate SDP algorithms for hybrid MDPs that empirically offers order-of- magnitude speedups over the exact solution in exchange for a small approximation error.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-vianna13a, title = {Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs}, author = {Vianna, Luis Gustavo and Sanner, Scott and de Barros, Leliane}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {232--241}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/vianna13a/vianna13a.pdf}, url = {https://proceedings.mlr.press/r11/vianna13a.html}, abstract = {Recent advances in symbolic dynamic pro- gramming (SDP) combined with the ex- tended algebraic decision diagram (XADD) data structure have provided exact solutions for mixed discrete and continuous (hybrid) MDPs with piecewise linear dynamics and continuous actions. Since XADD-based ex- act solutions may grow intractably large for many problems, we propose a bounded er- ror compression technique for XADDs that involves the solution of a constrained bilin- ear saddle point problem. Fortuitously, we show that given the special structure of this problem, it can be expressed as a bilevel lin- ear programming problem and solved to op- timality in finite time via constraint gener- ation, despite having an infinite set of con- straints. This solution permits the use of efficient linear program solvers for XADD compression and enables a novel class of bounded approximate SDP algorithms for hybrid MDPs that empirically offers order-of- magnitude speedups over the exact solution in exchange for a small approximation error.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs %A Luis Gustavo Vianna %A Scott Sanner %A Leliane de Barros %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-vianna13a %I PMLR %P 232--241 %U https://proceedings.mlr.press/r11/vianna13a.html %V R11 %X Recent advances in symbolic dynamic pro- gramming (SDP) combined with the ex- tended algebraic decision diagram (XADD) data structure have provided exact solutions for mixed discrete and continuous (hybrid) MDPs with piecewise linear dynamics and continuous actions. Since XADD-based ex- act solutions may grow intractably large for many problems, we propose a bounded er- ror compression technique for XADDs that involves the solution of a constrained bilin- ear saddle point problem. Fortuitously, we show that given the special structure of this problem, it can be expressed as a bilevel lin- ear programming problem and solved to op- timality in finite time via constraint gener- ation, despite having an infinite set of con- straints. This solution permits the use of efficient linear program solvers for XADD compression and enables a novel class of bounded approximate SDP algorithms for hybrid MDPs that empirically offers order-of- magnitude speedups over the exact solution in exchange for a small approximation error. %Z Reissued by PMLR on 04 October 2026.
APA
Vianna, L.G., Sanner, S. & de Barros, L.. (2013). Bounded Approximate Symbolic Dynamic Programming for Hybrid MDPs. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:232-241 Available from https://proceedings.mlr.press/r11/vianna13a.html. Reissued by PMLR on 04 October 2026.

Related Material