Adaptive Thompson Sampling Stacks for Memory Bounded Open-Loop Planning

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

TL;DR

This paper introduces SYMBOL, a novel open-loop planning algorithm for Partially Observable Markov Decision Processes (POMDPs) that efficiently manages memory by adaptively adjusting the size of its planning components. SYMBOL demonstrates competitive performance against state-of-the-art methods, particularly in memory-constrained scenarios, by leveraging Thompson Sampling bandits.

What Problem Does This Paper Address?

Decision-making in real-world scenarios often involves uncertainty about the environment's true state, a problem well-modeled by Partially Observable Markov Decision Processes (POMDPs). However, solving POMDPs exactly is computationally intractable for complex problems with large state spaces and long planning horizons due to the "curse of dimensionality" and "curse of history." While Monte-Carlo planning methods like POMCP offer efficient solutions by using search trees, these trees can become prohibitively large, especially in resource-constrained environments like sensor networks or IoT devices. Open-loop planning offers an alternative by optimizing action sequences independently of belief states, which can be more efficient but often leads to suboptimal solutions. This paper addresses the challenge of achieving efficient and robust planning in large POMDPs under memory constraints, aiming to bridge the gap between the computational demands of closed-loop methods and the suboptimality of traditional open-loop approaches.

Methods

The core contribution is SYMBOL (Stable Yet Memory Bounded Open-Loop) planning. SYMBOL is an open-loop planning algorithm that uses an adaptive stack of Thompson Sampling bandits. Instead of a fixed-size stack of statistics, SYMBOL dynamically adjusts the number of bandits based on the problem's complexity and convergence.

Here's how it works:

  • Thompson Sampling Bandits: Each bandit models the expected reward of an action at a specific time step. Thompson Sampling is used to balance exploration (trying new actions to learn their rewards) and exploitation (choosing actions with known high rewards). This is a Bayesian approach that uses prior beliefs and observed rewards to infer posterior distributions for action values.
  • Adaptive Stack: The number of bandits in the stack (nMAB) is not fixed beforehand. It starts with one bandit and grows as needed, up to the planning horizon T. The growth of the stack is managed by convergence criteria (ε and κ). A bandit is considered "converged" when its estimated reward difference falls below a threshold ε.
  • Convergence-Driven Adaptation: A new bandit is created only when the current bandit's convergence criterion is met and the current time step is less than the planning horizon. This ensures that the bandits adapt to the underlying domain without prior knowledge.
  • Rollout Policy: For time steps beyond the current number of bandits, SYMBOL uses a rollout policy (either random or domain-informed) to simulate future actions and their outcomes.
  • Memory Bounding: The size of the bandit stack is inherently bounded by the planning horizon T, and the adaptive nature ensures it doesn't unnecessarily grow large.

This approach contrasts with previous fixed-size stack methods (like POSTS) by allowing the stack size to adapt, potentially leading to more efficient memory usage and better performance.

Datasets

The paper evaluates SYMBOL on four established POMDP benchmark problems:

  • RockSample(n,k): Simulates an agent navigating a grid to find "good" rocks while avoiding "bad" ones, with noisy sensors.
  • Battleship: An agent must sink ships on a grid without knowing their positions, using a penalty for time steps and rewards for sinking ships.
  • PocMan: A partially observable version of Pac-Man where the agent navigates a maze, eats food, and avoids ghosts, with limited perception of ghosts and walls.

No new benchmarks were introduced; the focus was on evaluating SYMBOL's performance on existing, challenging POMDP domains.

Key Insights and Ideas

  • Adaptive Memory is Key: The most significant insight is that dynamically adapting the planning components (the number of Thompson Sampling bandits) is crucial for efficient memory usage in POMDPs. A fixed-size stack might be too large or too small, leading to suboptimal performance or wasted resources.
  • SYMBOL's Robustness: SYMBOL demonstrates robustness to hyperparameter choices (like the convergence threshold ε), suggesting it's a practical algorithm that doesn't require extensive tuning.
  • Open-Loop's Potential in POMDPs: The paper reinforces the idea that open-loop planning, when implemented intelligently (like with adaptive Thompson Sampling), can be a powerful alternative to closed-loop methods, especially when computational resources are limited.
  • Convergence as a Control Mechanism: Using convergence criteria for individual bandits to drive the adaptation of the stack size is an elegant way to manage complexity and ensure stability.

Key Results

  • Competitive Performance: SYMBOL performs competitively with, and often outperforms, other open-loop planning algorithms (POOLUCT, POOLTS, POSTS) and can keep up with the state-of-the-art closed-loop planner POMCP in several domains.
  • Memory Efficiency: In memory-constrained scenarios, SYMBOL significantly outperforms tree-based methods like POMCP and POOLTS, often using a much smaller number of MABs than the maximum allowed by the planning horizon. For instance, in RockSample, SYMBOL used around 20 MABs while POSTS required 100 to achieve comparable performance.
  • Scalability: SYMBOL scales better with increasing computation budgets (nb) than fixed-stack approaches like POSTS, which tend to converge prematurely.
  • Domain Adaptability: The adaptive stack size (nMAB) is highly domain-dependent and cannot be easily prespecified, highlighting the value of SYMBOL's adaptive approach. For example, the stack size varied significantly across RockSample, Battleship, and PocMan.

Limitations and Future Work

  • Prior Knowledge: While SYMBOL doesn't require domain knowledge beyond a generative model for planning, the choice of prior distributions for the Thompson Sampling bandits can influence performance. The paper suggests using uninformative priors when domain knowledge is scarce.
  • Hyperparameter Tuning: Although robust, some hyperparameters (like ε and κ) still influence performance and memory usage, and their optimal values are domain-dependent.
  • Future Work: The authors propose integrating SYMBOL into hierarchical planning frameworks to optimize macro-actions for specific subgoals, suggesting a path towards more complex and efficient planning strategies.

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