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.
Core Components
- 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.
- 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.
- 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