Near-Optimal BRL using Optimistic Local Transitions
This work addresses the exploration-exploitation dilemma in BRL for researchers, but it is incremental as it builds on existing heuristic approaches.
The paper tackles the combinatorial explosion in model-based Bayesian Reinforcement Learning (BRL) by introducing BOLT, an optimistic heuristic algorithm, and shows that it achieves near-optimal performance in the Bayesian sense with high probability under certain parameters.
Model-based Bayesian Reinforcement Learning (BRL) allows a found formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work relies on heuristic algorithms. This paper introduces BOLT, a simple and (almost) deterministic heuristic algorithm for BRL which is optimistic about the transition function. We analyze BOLT's sample complexity, and show that under certain parameters, the algorithm is near-optimal in the Bayesian sense with high probability. Then, experimental results highlight the key differences of this method compared to previous work.