Restricted Value Iteration: Theory and Algorithms
arXiv:1107.0042 · doi:10.1613/jair.1379
Abstract
Value iteration is a popular algorithm for finding near optimal policies for POMDPs. It is inefficient 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.
References in corpus (6)
- Value-Function Approximations for Partially Observable Markov Decision Processes
- Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
- Policy Iteration for Factored MDPs
- Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes
- Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems
- Structured Reachability Analysis for Markov Decision Processes