Adaptive Thompson Sampling Stacks for Memory Bounded Open-Loop Planning

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

This paper introduces SYMBOL (Stable Yet Memory Bounded Open-Loop) planning, a novel approach for decision-making in complex, partially observable environments. By using an adaptive stack of Thompson Sampling bandits, SYMBOL provides a memory-efficient alternative to traditional tree-based planning, automatically scaling its complexity to match the problem at hand without requiring prior domain knowledge.

TL;DR

SYMBOL is a memory-bounded planning algorithm for POMDPs that replaces massive search trees with an adaptive stack of Thompson Sampling bandits. It achieves competitive performance with state-of-the-art methods like POMCP while using orders of magnitude less memory, making it ideal for resource-constrained systems like IoT devices.

What Problem Does This Paper Address?

Planning in Partially Observable Markov Decision Processes (POMDPs) is notoriously difficult due to two "curses": the curse of dimensionality (the space of possible beliefs about the world is huge) and the curse of history (the number of possible action-observation sequences grows exponentially over time).

Modern algorithms like POMCP use Monte-Carlo tree search to handle these, but they often build massive search trees that can exhaust the memory of small devices (e.g., sensor networks). Open-loop planning—which optimizes sequences of actions regardless of specific observations—is more memory-efficient but often struggles with stability and convergence. The authors aim to bridge this gap by creating an open-loop planner that is both stable and strictly memory-bounded.

Methods

The core of SYMBOL is an adaptive stack of Multi-Armed Bandits (MABs). Instead of a tree, SYMBOL maintains a sequence of bandits, where each bandit $N_t$ is responsible for choosing the best action at time step $t$.

Key innovations include:

  • Generalized Thompson Sampling: SYMBOL uses a Bayesian approach to balance exploration and exploitation, assuming rewards follow a Normal distribution with unknown mean and precision.
  • Adaptive Stack Growth: The stack starts with just one bandit. A new bandit for the next time step is only added once all preceding bandits in the stack have "converged" (i.e., their suggested action values have stabilized).
  • Stationarity Guarantee: By waiting for predecessors to converge before updating or adding successors, SYMBOL ensures that each bandit faces a stationary reward distribution, which is a mathematical requirement for Thompson Sampling to converge properly.

The difference between traditional tree-based planning and SYMBOL's stacked approach is illustrated in Figure 1:

Figure 1: Illustration of closed- and open-loop planning schemes. (a) Closed-loop tree with state observations (circular nodes) and ac- tions (rectangular nodes). Red links correspond to stochastic obser- vations made with a probability of 0.5. (b) Open-loop tree with links as actions and history distribution nodes according to the blue dotted ellipses in Fig. 1a. (c) Open-loop approach with a stack of action distributions according to the blue dotted ellipses in Fig. 1b.

Datasets

The authors evaluated SYMBOL on three classic, large-scale POMDP benchmarks:

  1. RockSample($n,k$): An agent must navigate a grid to sample "good" rocks while avoiding "bad" ones using a noisy long-range sensor.
  2. Battleship: The agent must sink hidden ships on a $10 \times 10$ grid with minimal moves.
  3. PocMan: A partially observable version of PacMan where the agent has limited sight and hearing to detect ghosts and food in a large maze.

Key Insights and Ideas

  • Stability through Sequential Convergence: The most clever part of SYMBOL is the "wait-your-turn" approach to learning. By keeping successor bandits stationary until predecessors converge, the algorithm avoids the "moving target" problem common in multi-stage learning.
  • Automatic Complexity Scaling: You don't need to tell SYMBOL how deep to plan. It adds bandits to its stack based on the complexity of the domain and the available computational budget.
  • Memory Efficiency as a First-Class Citizen: While tree-based methods like POMCP grow linearly with the number of simulations, SYMBOL’s memory usage is strictly bounded by the planning horizon $T$. In practice, it often uses far fewer bandits than the maximum horizon.

Key Results

SYMBOL was compared against POMCP (a state-of-the-art closed-loop planner) and several open-loop variants (POOLTS, POOLUCT, and POSTS).

  • Performance vs. Memory: In RockSample and Battleship, SYMBOL outperformed or matched POMCP while using significantly less memory. As shown in Figure 3 (below), SYMBOL reaches peak performance with just ~20-30 MABs, whereas tree-based methods require thousands of nodes to achieve similar results.
  • Robustness: SYMBOL proved robust to hyperparameter choices (like the convergence threshold $\epsilon$).
  • High Stochasticity: In the highly stochastic PocMan domain, POMCP eventually outperforms SYMBOL if given enough memory, but SYMBOL remains the superior choice when memory is strictly limited (e.g., $< 100$ nodes).
Performance-memory tradeoff across different domains. Vertical lines show the max MABs used by SYMBOL.

Limitations and Future Work

The primary limitation is inherent to open-loop planning: in environments with very high stochasticity (like PocMan), ignoring specific observations during the planning phase eventually leads to suboptimality compared to closed-loop tree search.

For future work, the authors suggest integrating SYMBOL into hierarchical planning frameworks. This would allow SYMBOL to optimize high-level "macro-actions," potentially combining the memory efficiency of the stacked approach with the strategic depth of hierarchical reasoning.

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},
}

Loading related content...

Figure