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

Nevin L. Zhang lzhang@cs.ust.hk
Weihong Zhang wzhang@cs.ust.hk
Department of Computer Science
Hong Kong University of Science & Technology
Clear Water Bay Road, Kowloon, Hong Kong, CHINA

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.

• Introduction
• POMDPs and Value Iteration
  • POMDPs
  • Policies and Value Functions
  • Value Iteration
  • Technical and Notational Considerations
  • Finite Representation of Value Functions and Value Iteration
• Point-Based DP Update: The Idea
  • The Backup Operator
  • Point-Based DP Update
  • The Use of Point-Based DP Update
• Uniformly Improvable Value Functions
• Point-Based DP Update: The Algorithm
  • Backing Up on Witness Points of Input Vectors
  • Retaining Uniform Improvability
  • The Algorithm
  • Stopping Point-Based Value Iteration
  • Convergence of Modified Value Iteration
  • Computing the Bellman Residual
• Empirical Results and Discussions
• Variations of Point-Based DP Update
  • Improving the Quality of Point-Based DP Update
  • Reducing the Complexity of Point-Based DP Update
• Related Work
  • Point-Based DP Update and Standard DP Update
  • Point-Based Value Iteration and Value Function Approximation
  • Previous Work Related to Modified Value Iteration
• Conclusions and Future Directions
• About this document ...