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.
@cite_5: We introduce Stacked Thompson Bandits (STB) for efficiently generating plans that are likely to satisfy a given bounded temporal logic requirement. STB uses a simulation for evaluation of plans, and takes a Bayesian approach to using the resulting information to guide its search. In particular, we show that stacking multiarmed bandits and using Thompson sampling to guide the action selection process for each bandit enables STB to generate plans that satisfy requirements with a high probability while only searching a fraction of the search space.
@cite_12: 
@cite_3: We focus on effective sample-based planning in the face of underactuation, high-dimensionality, drift, discrete system changes, and stochasticity. These are hallmark challenges for important problems, such as humanoid locomotion. In order to ensure broad applicability, we assume domain expertise is minimal and limited to a generative model. In order to make the method responsive, computational costs that scale linearly with the amount of samples taken from the generative model are required. We bring to bear a concrete method that satisfies all these requirements; it is a receding-horizon open-loop planner that employs cross-entropy optimization for policy construction. In simulation, we empirically demonstrate near-optimal decisions in a small domain and effective locomotion in several challenging humanoid control tasks.
Previous stack based approaches to open-loop planning maintain a fixed size stack of @math statistics over actions to sample open-loop plans with high expected return @cite_3 @cite_5 @cite_12 . While these approaches work well in practice, their convergence properties remain unclear because of the non-stationarity of the sampling statistics and the underlying state distributions due to the simultaneous adaptation of each statistic. Furthermore, the required number of statistics is highly domain dependent and hard to prespecify. SYMBOL maintains an of Thompson Sampling bandits, which automatically adjusts its size according to the underlying domain without prior domain knowledge. The creation and adaptation of each bandit depends on the bandits to preserve a stationary state and reward distribution for proper convergence of all bandits.