ML Anthology

Efficient Planning in Large POMDPs Through Policy Graph Based Factorized Approximations

Joni Pajarinen, Jaakko Peltonen, Ari Hottinen, Mikko A. Uusitalo
ECML-PKDD 2010 pp. 1-16
doi:10.1007/978-3-642-15939-8_1 /ecmlpkdd/2010/pajarinen2010ecmlpkdd-efficient/

Abstract

Partially observable Markov decision processes (POMDPs) are widely used for planning under uncertainty. In many applications, the huge size of the POMDP state space makes straightforward optimization of plans (policies) computationally intractable. To solve this, we introduce an efficient POMDP planning algorithm. Many current methods store the policy partly through a set of “value vectors” which is updated at each iteration by planning one step further; the size of such vectors follows the size of the state space, making computation intractable for large POMDPs. We store the policy as a graph only, which allows tractable approximations in each policy update step: for a state space described by several variables, we approximate beliefs over future states with factorized forms, minimizing Kullback-Leibler divergence to the non-factorized distributions. Our other speedup approximations include bounding potential rewards. We demonstrate the advantage of our method in several reinforcement learning problems, compared to four previous methods.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Pajarinen et al. "Efficient Planning in Large POMDPs Through Policy Graph Based Factorized Approximations." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010. doi:10.1007/978-3-642-15939-8_1

Markdown

[Pajarinen et al. "Efficient Planning in Large POMDPs Through Policy Graph Based Factorized Approximations." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010.](https://mlanthology.org/ecmlpkdd/2010/pajarinen2010ecmlpkdd-efficient/) doi:10.1007/978-3-642-15939-8_1

BibTeX

@inproceedings{pajarinen2010ecmlpkdd-efficient,
  title     = {{Efficient Planning in Large POMDPs Through Policy Graph Based Factorized Approximations}},
  author    = {Pajarinen, Joni and Peltonen, Jaakko and Hottinen, Ari and Uusitalo, Mikko A.},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2010},
  pages     = {1-16},
  doi       = {10.1007/978-3-642-15939-8_1},
  url       = {https://mlanthology.org/ecmlpkdd/2010/pajarinen2010ecmlpkdd-efficient/}
}