Optimal Learning in High Dimensions

Abstract

Collecting information in the course of sequential decision-making can be extremely challenging in high-dimensional settings, where the number of measurement budget is much smaller than both the number of alternatives and the number of parameters in the model. In the parametric setting, we derive a knowledge gradient policy with high-dimensional sparse additive belief models, where there are hundreds or even thousands of features, but only a small portion of these features contain explanatory power. This policy is a unique and novel hybrid of Bayesian ranking and selection with a frequentist learning approach called Lasso. Particularly, our method naturally combines a B-spline basis of finite order and approximates the nonparametric additive model and functional ANOVA model. Theoretically, we provide the estimation error bounds of the posterior mean estimate and the functional estimate. We also demonstrate how this method is applied to learn the structure of large RNA molecules. In the nonparametric setting, we explore high-dimensional sparse belief functions, without putting any assumptions on the model structure. A knowledge gradient policy in the framework of regularized regression trees is developed. This policy provides an effective and efficient method for sequential information collection as well as feature selection for nonparametric belief models. We also show how this method can be used in two clinical settings: identifying optimal clinical pathways for patients, and reducing medical expenses in finding the best doctors for a sequence of patients.