One of the major challenges in applying machine learning-based optimization algorithms in practice is their efficiency, which is measured in runtime and sample efficiency. Unfortunately, these two measures do not go hand in hand, but there are two poles: model-based Reinforcement Learning (RL), which is fast but requires many calls to some oracle, and Bayesian Optimization (BO), which has a high computation time but is very sample efficient. Additionally, both methods are at risk of oracle-misspecification: the oracle used for learning may differ from the final application. We derive Graph Gaussian Process Monte Carlo Tree Search (GUMTREES), an algorithm combining Monte Carlo Tree Search (MCTS), a model-based RL method, with BO, leading to an efficient algorithm that is easily enhanced to the robust setting. In a simple experiment, we demonstrate the superior performance of our algorithm.