Conference Proceeding Article
While POMDPs (partially observable markov decision problems) are a popular computational model with wide-ranging applications, the computational cost for optimal policy generation is prohibitive. Researchers are investigating ever-more efficient algorithms, yet many applications demand such algorithms bound any loss in policy quality when chasing efficiency. To address this challenge, we present two new techniques. The first approximates in the value space to obtain solutions efficiently for a pre-specified error bound. Unlike existing techniques, our technique guarantees the resulting policy will meet this bound. Furthermore, it does not require costly computations to determine the quality loss of the policy. Our second technique prunes large tracts of belief space that are unreachable, allowing faster policy computation without any sacrifice in optimality. The combination of the two techniques, which are complementary to existing optimal policy generation algorithms, provides solutions with tight error bounds efficiently in domains where competing algorithms fail to provide such tight bounds.
Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Decision Analytics
IJCAI '07: Proceedings of the 20th International Joint Conference on Artifical Intelligence: Hyderabad, India, 6-12 January 2007
City or Country
Menlo Park, CA
VARAKANTHAM, Pradeep Reddy; Maheswaran, Rajiv; GUPTA, Tapana; and Tambe, Milind.
Towards Efficient Computation of Quality Bounded Solutions in POMDPs: Expected Value Approximation and Dynamic Disjunctive Beliefs. (2007). IJCAI '07: Proceedings of the 20th International Joint Conference on Artifical Intelligence: Hyderabad, India, 6-12 January 2007. 2683-2643. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/956
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.