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 programming (SDP) combined with the extended 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 exact solutions may grow intractably large for many problems, we propose a bounded error compression technique for XADDs that involves the solution of a constrained bilinear saddle point problem. Fortuitously, we show that given the special structure of this problem, it can be expressed as a bilevel linear programming problem and solved to optimality in finite time via constraint generation, despite having an infinite set of constraints. 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 programming (SDP) combined with the extended 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 exact solutions may grow intractably large for many problems, we propose a bounded error compression technique for XADDs that involves the solution of a constrained bilinear saddle point problem. Fortuitously, we show that given the special structure of this problem, it can be expressed as a bilevel linear programming problem and solved to optimality in finite time via constraint generation, despite having an infinite set of constraints. 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 programming (SDP) combined with the extended 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 exact solutions may grow intractably large for many problems, we propose a bounded error compression technique for XADDs that involves the solution of a constrained bilinear saddle point problem. Fortuitously, we show that given the special structure of this problem, it can be expressed as a bilevel linear programming problem and solved to optimality in finite time via constraint generation, despite having an infinite set of constraints. 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