Reinforcement Learning Trees for Sparse High-Dimensional Prediction

• Activity Number: 6
• Type: Invited
• Date/Time: Sunday, August 3, 2014 : 2:00 PM to 3:50 PM
• Sponsor: WNAR
• Author(s): Ruoqing Zhu*+ and Donglin Zeng and Michael Kosorok
• Companies: Yale and University of North Carolina at Chapel Hill and University of North Carolina at Chapel Hill
• Keywords: Tree-based ; Reinforcement Learning ; Random Forests ; Variable importance ; Convergence rate

Abstract

We introduce a new type of tree-based method, reinforcement learning trees (RLT), which exhibits significantly improved performance over traditional approaches. This new method implements reinforcement learning at each selection of a splitting variable during the tree construction processes. By splitting on the variable that brings the greatest future improvement in later splits, rather than choosing the one with the largest marginal effect from the immediate split, the constructed tree utilizes the available samples in a more efficient way. Moreover, such an approach enables linear combination cuts at little extra computational cost. We also propose a variable muting procedure that progressively eliminates noise variables during the construction of each individual tree. The muting procedure also takes advantage of reinforcement learning and prevents noise variables from being considered in the search for splitting rules when approaching terminal nodes. We investigate asymptotic properties of the proposed method under simple scenarios and also discuss the extension to right censored survival data.