Adaptive Thompson Sampling Stacks for Memory Bounded Open-Loop Planning
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.
Code (1)
Tasks
Thompson SamplingSimilar Papers 제목 키워드 기반
Memory Bounded Open-Loop Planning in Large POMDPs using Thompson Sampling
State-of-the-art approaches to partially observable planning like POMCP are based on stochastic tree search. While these approaches are computationally efficient, they may still construct search trees of considerable siz…
Thompson SamplingEfficient and Adaptive Posterior Sampling Algorithms for Bandits
We study Thompson Sampling-based algorithms for stochastic bandits with bounded rewards. As the existing problem-dependent regret bound for Thompson Sampling with Gaussian priors [Agrawal and Goyal, 2017] is vacuous when…
Thompson SamplingBatched Thompson Sampling
We introduce a novel anytime Batched Thompson sampling policy for multi-armed bandits where the agent observes the rewards of her actions and adjusts her policy only at the end of a small number of batches. We show that …
Multi-Armed BanditsThompson SamplingAdaptive Rate of Convergence of Thompson Sampling for Gaussian Process Optimization
We consider the problem of global optimization of a function over a continuous domain. In our setup, we can evaluate the function sequentially at points of our choice and the evaluations are noisy. We frame it as a conti…
global-optimizationThompson SamplingThompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewards
In this work, we study the performance of the Thompson Sampling algorithm for Contextual Bandit problems based on the framework introduced by Neu et al. and their concept of lifted information ratio. First, we prove a co…
Multi-Armed BanditsThompson Sampling