Approximate reinforcement learning: An overview <s> A. Offline value iteration <s> 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 (xt, ut , rt, xt+1) where xt denotes the system state at time t, ut the control action taken, rt the instantaneous reward obtained and xt+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. <s> BIB001 </s> Approximate reinforcement learning: An overview <s> A. Offline value iteration <s> We consider continuous state, continuous action batch reinforcement learning where the goal is to learn a good policy from a sufficiently rich trajectory generated by some policy. We study a variant of fitted Q-iteration, where the greedy action selection is replaced by searching for a policy in a restricted set of candidate policies by maximizing the average action values. We provide a rigorous analysis of this algorithm, proving what we believe is the first finite-time bound for value-function based algorithms for continuous state and action problems. <s> BIB002
In the offline, model-free case, a batch of transition samples is available: where for every j, the next state x j and the reward r j have been observed as a result of taking action u j in the state x j . The transition samples may be independent, they may belong to a set of trajectories, or to a single trajectory. A prominent example of offline, approximate value iteration is fitted Q-iteration BIB001 - BIB002 . To understand how this algorithm is obtained, consider first classical Q-iteration (Sec. II), but in the deterministic case. In this case, the dynamics simplify to x k+1 = f (x k , u k ), the reward function to r k+1 = ρ(x k , u k ), and the Q-iteration update becomes: To obtain fitted Q-iteration, three changes are made: (i) Since the exact Q-function Q (x, u) is unavailable, an approximate Q-function Q(x, u; θ ), parameterized by θ , is used instead. (ii) Target Q-values for the updates are only computed for the pairs (x j , u j ). For each j, the (unknown) f (x j , u j ) and ρ(x j , u j ) are replaced by the observations x j and r j , leading to the target Q-value sample: q targ +1,j = r j +γ max u Q(x j , u ; θ ). Because the system is deterministic, x j = f (x j , u j ) and r j = ρ(x j , u j ); thus, the replacements are exact. (Note also the similarity with the Q-learning update target in (6).) (iii) Rather than computing an entire updated Q-function Q +1 , regression is performed on the available samples, to find a new parameter vector θ +1 so that Q(x j , u j ; θ +1 ) ≈ q +1,j . Thus, the entire fitted Q-iteration update can be written: where the generic regression algorithm 'regr' can be instantiated, e.g., to least-squares regression. In the stochastic case, the target Q-value Q targ +1 (x j , u j ) is E x ∼f (xj ,uj ,·) ρ(x j , u j , x ) + γ max u Q(x , u ; θ ) , i.e., an expectation of a random variable, of which q targ +1,j is only a sample. Nevertheless, most regression algorithms, including least-squares, seek to approximate the expected value of their output variable conditioned by the input. This means that the regression actually looks for θ +1 such that Q(x, u; θ +1 ) ≈ Q targ +1 (x, u), and therefore the update (13) remains valid in the stochastic case.