Region-based value iteration for partially observable Markov decision processes

ABSTRACT

An approximate region-based value iteration (RBVI) algorithm is proposed to find the optimal policy for a partially observable Markov decision process (POMDP). The proposed RBVI approximates the true polyhedral partition of the belief simplex with an ellipsoidal partition, such that the optimal value function is linear in each of the ellipsoidal regions. The position and shape of each region, as well as the gradient (alpha-vector) of the optimal value function in the region, are parameterized explicitly, and are estimated via efficient expectation maximization (EM) and variational Bayesian EM (VBEM), based on a set of selected sample belief points. The RBVI maintains a much smaller number of alpha-vectors than point-based methods and yields a more parsimonious representation that approximates the true value function in the maximum likelihood (ML) sense. The results on benchmark problems show that the proposed RBVI is comparable in performance to state-of-the-art algorithms, despite of the small number of alpha-vectors that are used.

REFERENCES

• 1: Brafman, R. I. (1997). A heuristic variable grid solution method for pomdps. AAAI (pp. 727--733).
• 2: Hsien-Te Cheng , Shelby Brumelle, Algorithms for partially observable markov decision processes, 1989
• 3: Corduneanu, A., & Bishop, C. (2001). Variational Bayesian model selection for mixture distributions. AI and Statistics (pp. 27--34).
• 4: Leslie Pack Kaelbling , Michael L. Littman , Anthony R. Cassandra, Planning and acting in partially observable stochastic domains, Artificial Intelligence, v.101 n.1-2, p.99-134, May 1998 [doi>10.1016/S0004-3702(98)00023-X]
• 5: Littman, M. L., Cassandra, A. R., & Kaelbling, L. P. (1995). Learning policies for partially obsevable environments:scaling up. ICML (pp. 362--370).
• 6: William S. Lovejoy, Computationally feasible bounds for partially observed Markov decision processes, Operations Research, v.39 n.1, p.162-175, Jan./Feb. 1991 [doi>10.1287/opre.39.1.162]
• 7: Pineau, J., Gordon, G., & Thrun, S. (2003). Point-based value iteration: An anytime algorithm for POMDPs. IJ-CAI (pp. 1025 -- 1032).
• 8: Poon, K.-M. (2001). A fast heuristic algorithm for decision-theoretic planning. Master's thesis, The Hong Kong University of Science and Technology.
• 9: Poupart, P., & Boutilier, C. (2003). Bounded finite state controllers. NIPS.
• 10: Smallwood, R. D., & Sondik, E. J. (1973). The optimal control of partially observable Markov processes over a finite horizon. Operational Research, 21, 1071--1088.
• 11: Trey Smith , Reid Simmons, Heuristic search value iteration for POMDPs, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.520-527, July 07-11, 2004, Banff, Canada
• 12: Smith, T., & Simmons, R. (2005). Point-based POMDP algorithms: Improved analysis and implementation. Proc. of UAI.
• 13: Sondik, E. J. (1971). The optimal control of partially observable Markov processes. Doctoral dissertation, Stanford University.
• 14: Spaan, M., & Vlassis, N. (2004). A point-based POMDP algorithm for robot planning. Proc. IEEE Int. Conf. on Robotics and Automation (ICRA) (pp. 2399--2404).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms, Theory