On the Relationship Between Satisfiability and Markov Decision Processes
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
Text
Salmon and Poupart. "On the Relationship Between Satisfiability and Markov Decision Processes." Uncertainty in Artificial Intelligence, 2019.Markdown
[Salmon and Poupart. "On the Relationship Between Satisfiability and Markov Decision Processes." Uncertainty in Artificial Intelligence, 2019.](https://mlanthology.org/uai/2019/salmon2019uai-relationship/)BibTeX
@inproceedings{salmon2019uai-relationship,
title = {{On the Relationship Between Satisfiability and Markov Decision Processes}},
author = {Salmon, Ricardo and Poupart, Pascal},
booktitle = {Uncertainty in Artificial Intelligence},
year = {2019},
pages = {1105-1115},
volume = {115},
url = {https://mlanthology.org/uai/2019/salmon2019uai-relationship/}
}