Restricted Value Iteration: Theory and Algorithms
Abstract
Value iteration is a popular algorithm for finding near optimal policies for POMDPs. It is ineffcient due to the need to account for the entire belief space, which necessitates the solution of large numbers of linear programs. In this paper, we study value iteration restricted to belief subsets. We show that, together with properly chosen belief subsets, restricted value iteration yields near-optimal policies and we give a condition for determining whether a given belief subset would bring about savings in space and time. We also apply restricted value iteration to two interesting classes of POMDPs, namely informative POMDPs and near-discernible POMDPs.
Cite
Text
Zhang and Zhang. "Restricted Value Iteration: Theory and Algorithms." Journal of Artificial Intelligence Research, 2005. doi:10.1613/JAIR.1379Markdown
[Zhang and Zhang. "Restricted Value Iteration: Theory and Algorithms." Journal of Artificial Intelligence Research, 2005.](https://mlanthology.org/jair/2005/zhang2005jair-restricted/) doi:10.1613/JAIR.1379BibTeX
@article{zhang2005jair-restricted,
title = {{Restricted Value Iteration: Theory and Algorithms}},
author = {Zhang, Weihong and Zhang, Nevin Lianwen},
journal = {Journal of Artificial Intelligence Research},
year = {2005},
pages = {123-165},
doi = {10.1613/JAIR.1379},
volume = {23},
url = {https://mlanthology.org/jair/2005/zhang2005jair-restricted/}
}