Sparse stochastic finite-state controllers for POMDPs

Eric A. Hansen
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:256-263, 2008.

Abstract

Bounded policy iteration is an approach to solving infinite-horizon POMDPs that represents policies as stochastic finite-state controllers and iteratively improves a controller by adjusting the parameters of each node using linear programming. In the original algorithm, the size of the linear programs, and thus the complexity of policy improvement, depends on the number of parameters of each node, which grows with the size of the controller. But in practice, the number of parameters of a node with non-zero values is often very small, and does not grow with the size of the controller. Based on this observation, we develop a version of bounded policy iteration that leverages the sparse structure of a stochastic finite-state controller. In each iteration, it improves a policy by the same amount as the original algorithm, but with much better scalability.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-hansen08a, title = {Sparse stochastic finite-state controllers for POMDPs}, author = {Hansen, Eric A.}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {256--263}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/hansen08a/hansen08a.pdf}, url = {https://proceedings.mlr.press/r6/hansen08a.html}, abstract = {Bounded policy iteration is an approach to solving infinite-horizon POMDPs that represents policies as stochastic finite-state controllers and iteratively improves a controller by adjusting the parameters of each node using linear programming. In the original algorithm, the size of the linear programs, and thus the complexity of policy improvement, depends on the number of parameters of each node, which grows with the size of the controller. But in practice, the number of parameters of a node with non-zero values is often very small, and does not grow with the size of the controller. Based on this observation, we develop a version of bounded policy iteration that leverages the sparse structure of a stochastic finite-state controller. In each iteration, it improves a policy by the same amount as the original algorithm, but with much better scalability.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T Sparse stochastic finite-state controllers for POMDPs %A Eric A. Hansen %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-hansen08a %I PMLR %P 256--263 %U https://proceedings.mlr.press/r6/hansen08a.html %V R6 %X Bounded policy iteration is an approach to solving infinite-horizon POMDPs that represents policies as stochastic finite-state controllers and iteratively improves a controller by adjusting the parameters of each node using linear programming. In the original algorithm, the size of the linear programs, and thus the complexity of policy improvement, depends on the number of parameters of each node, which grows with the size of the controller. But in practice, the number of parameters of a node with non-zero values is often very small, and does not grow with the size of the controller. Based on this observation, we develop a version of bounded policy iteration that leverages the sparse structure of a stochastic finite-state controller. In each iteration, it improves a policy by the same amount as the original algorithm, but with much better scalability. %Z Reissued by PMLR on 09 October 2024.
APA
Hansen, E.A.. (2008). Sparse stochastic finite-state controllers for POMDPs. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:256-263 Available from https://proceedings.mlr.press/r6/hansen08a.html. Reissued by PMLR on 09 October 2024.

Related Material