A Novel Orthogonal NMF-Based Belief Compression for POMDPs

A Novel Orthogonal NMF-Based Belief Compression for POMDPs
Xin Li - Computer Science Department, Hong Kong Baptist University, Hong Kong, China William K. W. Cheung - Computer Science Department, Hong Kong Baptist University, Hong Kong, China Jiming Liu - Computer Science Department, Hong Kong Baptist University, Hong Kong, China Zhili Wu - Computer Science Department, Hong Kong Baptist University, Hong Kong, China
High dimensionality of POMDP's belief state space is one ma jor cause that makes the underlying optimal policy computation intractable. Belief compression refers to the methodology that pro jects the belief state space to a low-dimensional one to alleviate the problem. In this paper, we propose a novel orthogonal non-negative matrix factorization (O-NMF) for the pro jection. The proposed O-NMF not only factors the belief state space by minimizing the reconstruction error, but also allows the compressed POMDP formulation to be efficiently computed (due to its orthogonality) in a valuedirected manner so that the value function will take same values for corresponding belief states in the original and compressed state spaces. We have tested the proposed approach using a number of benchmark problems and the empirical results confirms its effiectiveness in achieving substantial computational cost saving in policy computation.

Xin Li - Computer Science Department, Hong Kong Baptist University, Hong Kong, China
William K. W. Cheung - Computer Science Department, Hong Kong Baptist University, Hong Kong, China
Jiming Liu - Computer Science Department, Hong Kong Baptist University, Hong Kong, China
Zhili Wu - Computer Science Department, Hong Kong Baptist University, Hong Kong, China

High dimensionality of POMDP's belief state space is one ma jor cause that makes the underlying optimal policy computation intractable. Belief compression refers to the methodology that pro jects the belief state space to a low-dimensional one to alleviate the problem. In this paper, we propose a novel orthogonal non-negative matrix factorization (O-NMF) for the pro jection. The proposed O-NMF not only factors the belief state space by minimizing the reconstruction error, but also allows the compressed POMDP formulation to be efficiently computed (due to its orthogonality) in a valuedirected manner so that the value function will take same values for corresponding belief states in the original and compressed state spaces. We have tested the proposed approach using a number of benchmark problems and the empirical results confirms its effiectiveness in achieving substantial computational cost saving in policy computation.