Memory Bounded Open-Loop Planning in Large POMDPs Using Thompson Sampling

Authors

  • Thomy Phan Ludwig Maximilian University of Munich
  • Lenz Belzner MaibornWolff
  • Marie Kiermeier Ludwig Maximilian University of Munich
  • Markus Friedrich Ludwig Maximilian University of Munich
  • Kyrill Schmid Ludwig Maximilian University of Munich
  • Claudia Linnhoff-Popien Virality GmbH

DOI:

https://doi.org/10.1609/aaai.v33i01.33017941

Abstract

State-of-the-art approaches to partially observable planning like POMCP are based on stochastic tree search. While these approaches are computationally efficient, they may still construct search trees of considerable size, which could limit the performance due to restricted memory resources. In this paper, we propose Partially Observable Stacked Thompson Sampling (POSTS), a memory bounded approach to openloop planning in large POMDPs, which optimizes a fixed size stack of Thompson Sampling bandits. We empirically evaluate POSTS in four large benchmark problems and compare its performance with different tree-based approaches. We show that POSTS achieves competitive performance compared to tree-based open-loop planning and offers a performancememory tradeoff, making it suitable for partially observable planning with highly restricted computational and memory resources.

Downloads

Published

2019-07-17

How to Cite

Phan, T., Belzner, L., Kiermeier, M., Friedrich, M., Schmid, K., & Linnhoff-Popien, C. (2019). Memory Bounded Open-Loop Planning in Large POMDPs Using Thompson Sampling. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 7941-7948. https://doi.org/10.1609/aaai.v33i01.33017941

Issue

Section

AAAI Technical Track: Reasoning under Uncertainty