Adaptive Thompson Sampling Stacks for Memory Bounded Open-Loop Planning

Thomy Phan, Thomas Gabor, Robert Müller, Christoph Roch, Claudia Linnhoff-Popien

Introduction

Decision-making in uncertain environments is often modeled as a Partially Observable Markov Decision Process (POMDP). In these scenarios, agents must plan actions based on a "belief" state derived from noisy observations. While state-of-the-art "closed-loop" algorithms like POMCP are highly effective, they rely on massive search trees that suffer from the "curse of dimensionality" and the "curse of history." These trees can quickly exhaust the memory of resource-constrained devices, such as IoT sensors or mobile robots.

The SYMBOL Algorithm

To address these memory constraints, the authors propose SYMBOL (Stable Yet Memory Bounded Open-Loop) planning. SYMBOL bridges the gap between simple action-sequence optimization and complex, memory-heavy search trees by utilizing an Adaptive Thompson Sampling Stack.

Comparison of (a) closed-loop tree, (b) open-loop tree, and (c) stacked planning architectures.

Core Components

  1. The Stack Architecture: Unlike tree-based methods that branch for every possible observation, SYMBOL maintains a vertical stack of Multi-Armed Bandits (MABs). Each bandit in the stack is responsible for selecting the optimal action for a specific future time step.
  2. Generalized Thompson Sampling: Each bandit employs a Bayesian approach using a Normal-Gamma distribution to estimate rewards. This allows the algorithm to handle arbitrary reward ranges without the need for extensive prior tuning.
  3. Stability-Driven Growth: The stack begins with a single bandit. A new bandit is added to extend the planning horizon only after all preceding bandits in the stack have "converged" (controlled by a threshold $\epsilon$). This ensures that each bandit faces a stationary environment, which is a mathematical requirement for bandit convergence.

Experimental Evaluation

The researchers evaluated SYMBOL against standard benchmarks including RockSample (11,11) and (15,15), Battleship, and PocMan (a partially observable variant of Pac-Man).

Key Results

  • Memory Efficiency: In the RockSample domain, SYMBOL achieved peak performance using only 20-30 MABs. In contrast, tree-based methods required thousands of nodes to achieve comparable results.
  • Performance: SYMBOL consistently outperformed POOLUCT (an open-loop tree search) and remained competitive with the state-of-the-art POMCP in RockSample and Battleship.
  • Scalability: SYMBOL's adaptive growth mechanism allows it to scale more effectively than fixed-size stacks, which often converge prematurely or fail to find deep solutions.

Discussion and Limitations

While SYMBOL excels in memory efficiency, it faces challenges in highly stochastic environments. In PocMan, where ghost movements are random, the closed-loop nature of POMCP eventually provides an advantage because it can react to specific observations during the planning phase. Additionally, like most Monte-Carlo methods, SYMBOL requires a generative model (simulator) of the environment to function.

Conclusion

SYMBOL demonstrates that a simple, adaptive stack of bandits can provide a powerful and memory-efficient alternative to traditional search trees for open-loop planning. By prioritizing stability in stack growth, it offers a robust solution for planning on resource-constrained hardware.

Reference: Phan, T., Gabor, T., Müller, R., Roch, C., & Linnhoff-Popien, C. (2019). Adaptive Thompson Sampling Stacks for Memory Bounded Open-Loop Planning. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI-19).

Summary updated

Abstract

We propose Stable Yet Memory Bounded Open-Loop (SYMBOL) planning, a general memory bounded approach to partially observable open-loop planning. SYMBOL maintains an adaptive stack of Thompson Sampling bandits, whose size is bounded by the planning horizon and can be automatically adapted according to the underlying domain without any prior domain knowledge beyond a generative model. We empirically test SYMBOL in four large POMDP benchmark problems to demonstrate its effectiveness and robustness w.r.t. the choice of hyperparameters and evaluate its adaptive memory consumption. We also compare its performance with other open-loop planning algorithms and POMCP.
BibTeX
@inproceedings{phan2019adaptive,
  author = {Thomy Phan and Thomas Gabor and Robert Müller and Christoph Roch and Claudia Linnhoff-Popien},
  title = {{Adaptive Thompson Sampling Stacks for Memory Bounded Open-Loop Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/778},
}
Figure