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:
Datasets
The authors evaluated SYMBOL on three classic, large-scale POMDP benchmarks:
- RockSample($n,k$): An agent must navigate a grid to sample "good" rocks while avoiding "bad" ones using a noisy long-range sensor.
- Battleship: The agent must sink hidden ships on a $10 \times 10$ grid with minimal moves.
- 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).
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