Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions
Jihwan Jeong, Parth Jaggi, Scott Sanner
Abstract
Recent advances in symbolic dynamic programming (SDP) have significantly broadened the class of MDPs for which exact closed-form value functions can be derived. However, no existing solution methods can solve complex discrete and continuous state MDPs where a linear program determines state transitions --- transitions that are often required in problems with underlying constrained flow dynamics arising in problems ranging from traffic signal control to telecommunications bandwidth planning. In this paper, we present a novel SDP solution method for MDPs with LP transitions and continuous piecewise linear dynamics by introducing a novel, fully symbolic argmax operator. On three diverse domains, we show the first automated exact closed-form SDP solution to these challenging problems and the significant advantages of our SDP approach over discretized approximations.
BibTeX
@inproceedings{ijcai2021p562,
title = {Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions},
author = {Jeong, Jihwan and Jaggi, Parth and Sanner, Scott},
booktitle = {Proceedings of the Thirtieth International Joint Conference on
Artificial Intelligence, {IJCAI-21}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Zhi-Hua Zhou},
pages = {4083--4089},
year = {2021},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2021/562},
url = {https://doi.org/10.24963/ijcai.2021/562},
}