Abstraction Selection in Model-based Reinforcement Learning
Nan Jiang, Alex Kulesza, Satinder Pal Singh · 2015
State abstractions are often used to reduce the complexity of model-based reinforcement learn-ing when only limited quantities of data are avail-able. However, choosing the appropriate level of abstraction is an important problem in prac-tice. Existing approaches have theoretical guaran-tees only under strong assumptions on the domain or asymptotically large amounts of data, but in this paper we propose a simple algorithm based on statistical hypothesis testing that comes with a finite-sample guarantee under assumptions on candidate abstractions. Our algorithm trades off the low approximation error of finer abstractions against the low estimation error of coarser abstrac-tions, resulting in a loss bound that depends only on the quality of the best available abstraction and is polynomial in planning horizon. 1.