Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes

Abstract

Partially observable Markov decision processes (POMDPs) have recently become popular among many AI researchers because they serve as a natural model for planning under uncertainty. Value iteration is a well-known algorithm for finding optimal policies for POMDPs. It typically takes a large number of iterations to converge. This paper proposes a method for accelerating the convergence of value iteration. The method has been evaluated on an array of benchmark problems and was found to be very effective: It enabled value iteration to converge after only a few iterations on all the test problems.

References in corpus (4)

• Value-Function Approximations for Partially Observable Markov Decision Processes
• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
• Solving POMDPs by Searching in Policy Space
• A Method for Speeding Up Value Iteration in Partially Observable Markov Decision Processes

Cited by in corpus (7)

• Partially Observable Markov Decision Processes (POMDPs) and Robotics
• Point-Based POMDP Algorithms: Improved Analysis and Implementation
• Restricted Value Iteration: Theory and Algorithms
• Throughput Maximization for Ambient Backscatter Communication: A Reinforcement Learning Approach
• Suboptimality Bounds for Stochastic Shortest Path Problems
• On Polynomial Sized MDP Succinct Policies
• On Anderson acceleration for partially observable Markov decision processes