Model-based Bayesian Reinforcement Learning (BRL) allows a sound formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suer 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 nearoptimal in the Bayesian sense with high probability. Then, experimental results highlight the key dierences of this method compared to previous work.
['Mauricio Araya', 'Olivier Buffet', 'Vincent Thomas']
Near-Optimal BRL using Optimistic Local Transitions