Approximate reinforcement learning: An overview <s> B. Rollout-based policy evaluation <s> The basic tools of machine learning appear in the inner loop of most reinforcement learning algorithms, typically in the form of Monte Carlo methods or function approximation techniques. To a large extent, however, current reinforcement learning algorithms draw upon machine learning techniques that are at least ten years old and, with a few exceptions, very little has been done to exploit recent advances in classification learning for the purposes of reinforcement learning. We use a variant of approximate policy iteration based on rollouts that allows us to use a pure classification learner, such as a support vector machine (SVM), in the inner loop of the algorithm. We argue that the use of SVMs, particularly in combination with the kernel trick, can make it easier to apply reinforcement learning as an "out-of-the-box" technique, without extensive feature engineering. Our approach opens the door to modern classification methods, but does not preclude the use of classical methods. We present experimental results in the pendulum balancing and bicycle riding domains using both SVMs and neural networks for classifiers. <s> BIB001 </s> Approximate reinforcement learning: An overview <s> B. Rollout-based policy evaluation <s> Several researchers [2,3] have recently investigated the connection between reinforcement learning and classification. Our work builds on [2], which suggests an approximate policy iteration algorithm for learning a good policy represented as a classifier, without explicit value function representation. At each iteration, a new policy is produced using training data obtained through rollouts of the previous policy on a simulator. These rollouts aim at identifying better action choices over a subset of states in order to form a set of data for training the classifier representing the improved policy. Even though [2,3] examine how to distribute training states over the state space, their major limitation remains the large amount of sampling employed at each training state. ::: ::: We suggest methods to reduce the number of samples needed to obtain a high-quality training set. This is done by viewing the setting as akin to a bandit problem over the states from which rollouts are performed. Our contribution is two-fold: (a) we suitably adapt existing bandit techniques for rollout management, and (b) we suggest a more appropriate statistical test for identifying states with dominating actions early and with high confidence. Experiments on two classical domains (inverted pendulum, mountain car) demonstrate an improvement in sample complexity that substantially increases the applicability of rollout-based algorithms. In future work, we aim to obtain algorithms specifically tuned to this task with even lower sample complexity and to address the question of the choice of sampling distribution. <s> BIB002
Rollout-based algorithms for policy evaluation do not represent the value function explicitly, but evaluate it on demand, using Monte Carlo simulations. For example, to estimate the Q-value Q h (x, u) of a given state-action pair (x, u), a number N MC of trajectories are simulated, where each trajectory has length K and starts from the pair (x, u). The estimated Qvalue is then the average of the sample returns obtained along these trajectories: For each trajectory i 0 , the first state-action pair is fixed to (x, u) and leads to x i0,1 ∼ f (x, u, ·). Thereafter, actions are chosen using the policy h, thus This procedure is called a rollout BIB001 , BIB002 . Using rollouts can be computationally expensive, especially in the stochastic case, and the computational cost is proportional to the number of points at which the value function must be evaluated. Therefore, rollouts are most useful when this number is small, and Bellman-equation based methods may be preferable when the value function must be evaluated at many (or all) points.