[en] fitted Q iteration ; batch mode reinforcement learning ; ensemble of regression trees ; supervised learning ; fitted value iteration ; optimal control

[en] Reinforcement learning aims to determine an optimal control policy from interaction with a system or from observations gathered from a system. In batch mode, it can be achieved by approximating the so-called Q-function based on a set of four-tuples (x(t), u(t), r(t), x(t+1)) where x(t) denotes the system state at time t, u(t) the control action taken, r(t) the instantaneous reward obtained and x(t+1) the successor state of the system, and by determining the control policy from this Q-function. The Q-function approximation may be obtained from the limit of a sequence of (batch mode) supervised learning problems. Within this framework we describe the use of several classical tree-based supervised learning methods (CART, Kd-tree, tree bagging) and two newly proposed ensemble algorithms, namely extremely and totally randomized trees. We study their performances on several examples and find that the ensemble methods based on regression trees perform well in extracting relevant information about the optimal control policy from sets of four-tuples. In particular, the totally randomized trees give good results while ensuring the convergence of the sequence, whereas by relaxing the convergence constraint even better accuracy results are provided by the extremely randomized trees.

Fonds de la Recherche Scientifique (Communauté française de Belgique) - F.R.S.-FNRS

The fitted Q iteration (FQI) algorithm was first described in the paper "Iteratively extending time horizon reinforcement learning" (see below) but this paper is the first one to name it fitted Q iteration (or FQI in short).