On the Relationship Between Satisfiability and Markov Decision Processes

Ricardo Salmon, Pascal Poupart
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:1105-1115, 2020.

Abstract

Stochastic satisfiability (SSAT) and decision-theoretic planning in finite horizon partially observable Markov decision processes (POMDPs) are both PSPACE-Complete. We describe constructive reductions between SSAT and flat POMDPs that open the door to comparisons and future cross-fertilization between the solution techniques of those problems. We also propose a new SSAT solver called Prime that incorporates recent advances from the SAT and #SAT literature. Using our reduction from POMDP to SSAT, we demonstrate the competitiveness of Prime on finite horizon POMDP problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-salmon20a, title = {On the Relationship Between Satisfiability and Markov Decision Processes}, author = {Salmon, Ricardo and Poupart, Pascal}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {1105--1115}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/salmon20a/salmon20a.pdf}, url = {https://proceedings.mlr.press/v115/salmon20a.html}, abstract = {Stochastic satisfiability (SSAT) and decision-theoretic planning in finite horizon partially observable Markov decision processes (POMDPs) are both PSPACE-Complete. We describe constructive reductions between SSAT and flat POMDPs that open the door to comparisons and future cross-fertilization between the solution techniques of those problems. We also propose a new SSAT solver called Prime that incorporates recent advances from the SAT and #SAT literature. Using our reduction from POMDP to SSAT, we demonstrate the competitiveness of Prime on finite horizon POMDP problems.} }
Endnote
%0 Conference Paper %T On the Relationship Between Satisfiability and Markov Decision Processes %A Ricardo Salmon %A Pascal Poupart %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-salmon20a %I PMLR %P 1105--1115 %U https://proceedings.mlr.press/v115/salmon20a.html %V 115 %X Stochastic satisfiability (SSAT) and decision-theoretic planning in finite horizon partially observable Markov decision processes (POMDPs) are both PSPACE-Complete. We describe constructive reductions between SSAT and flat POMDPs that open the door to comparisons and future cross-fertilization between the solution techniques of those problems. We also propose a new SSAT solver called Prime that incorporates recent advances from the SAT and #SAT literature. Using our reduction from POMDP to SSAT, we demonstrate the competitiveness of Prime on finite horizon POMDP problems.
APA
Salmon, R. & Poupart, P.. (2020). On the Relationship Between Satisfiability and Markov Decision Processes. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:1105-1115 Available from https://proceedings.mlr.press/v115/salmon20a.html.

Related Material