TY - JOUR
T1 - Reinforcement Learning Trees
AU - Zhu, Ruoqing
AU - Zeng, Donglin
AU - Kosorok, Michael R.
N1 - Funding Information:
R. Zhu (E-mail: rqzhu@illinois.edu) is a student, D. Zeng (E-mail: dzeng@email.unc.edu) is Professor, and M. R. Kosorok (Email: Kosorok@unc.edu) is W. R. Kenan, Jr. Distinguished Professor and Chair, Department of Biostatistics, CB#7420, University of North Carolina, Chapel Hill, NC 27599-7420. The authors thank the editors and reviewers for their careful review and thoughtful suggestions, which led to a significantly improved article. The authors were funded in part by grants P01 CA142538 from the National Cancer Institute and U01 NS082062 from the National Institute of Neurological Disorders and Stroke.
PY - 2015/10/2
Y1 - 2015/10/2
N2 - In this article, we introduce a new type of tree-based method, reinforcement learning trees (RLT), which exhibits significantly improved performance over traditional methods such as random forests (Breiman 2001) under high-dimensional settings. The innovations are three-fold. First, the 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 largest marginal effect from the immediate split, the constructed tree uses the available samples in a more efficient way. Moreover, such an approach enables linear combination cuts at little extra computational cost. Second, we 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, so that toward terminal nodes, where the sample size is small, the splitting rules are still constructed from only strong variables. Last, we investigate asymptotic properties of the proposed method under basic assumptions and discuss rationale in general settings. Supplementary materials for this article are available online.
AB - In this article, we introduce a new type of tree-based method, reinforcement learning trees (RLT), which exhibits significantly improved performance over traditional methods such as random forests (Breiman 2001) under high-dimensional settings. The innovations are three-fold. First, the 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 largest marginal effect from the immediate split, the constructed tree uses the available samples in a more efficient way. Moreover, such an approach enables linear combination cuts at little extra computational cost. Second, we 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, so that toward terminal nodes, where the sample size is small, the splitting rules are still constructed from only strong variables. Last, we investigate asymptotic properties of the proposed method under basic assumptions and discuss rationale in general settings. Supplementary materials for this article are available online.
KW - Consistency
KW - Error bound
KW - Random forests
KW - Reinforcement learning
KW - Trees
UR - http://www.scopus.com/inward/record.url?scp=84954421092&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954421092&partnerID=8YFLogxK
U2 - 10.1080/01621459.2015.1036994
DO - 10.1080/01621459.2015.1036994
M3 - Article
C2 - 26903687
AN - SCOPUS:84954421092
VL - 110
SP - 1770
EP - 1784
JO - Journal of the American Statistical Association
JF - Journal of the American Statistical Association
SN - 0162-1459
IS - 512
ER -