Point-Based POMDP Algorithms: Improved Analysis and Implementation
Abstract
Existing complexity bounds for point-based POMDP value iteration algorithms focus either on the curse of dimensionality or the curse of history. We derive a new bound that relies on both and uses the concept of discounted reachability; our conclusions may help guide future algorithm design. We also discuss recent improvements to our (point-based) heuristic search value iteration algorithm. Our new implementation calculates tighter initial bounds, avoids solving linear programs, and makes more effective use of sparsity.
Cite
Text
Smith and Simmons. "Point-Based POMDP Algorithms: Improved Analysis and Implementation." Conference on Uncertainty in Artificial Intelligence, 2005.Markdown
[Smith and Simmons. "Point-Based POMDP Algorithms: Improved Analysis and Implementation." Conference on Uncertainty in Artificial Intelligence, 2005.](https://mlanthology.org/uai/2005/smith2005uai-point/)BibTeX
@inproceedings{smith2005uai-point,
title = {{Point-Based POMDP Algorithms: Improved Analysis and Implementation}},
author = {Smith, Trey and Simmons, Reid G.},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2005},
pages = {542-547},
url = {https://mlanthology.org/uai/2005/smith2005uai-point/}
}