Decision-makers increasingly have access to rich customer-specific data, providing an opportunity to make better, personalized service decisions. For example, in healthcare, doctors can personalize interventions based on a patient's clinical history; in marketing, companies can target ads based on customer purchase history. However, the increased variety of potentially relevant customer data implies that an individual's covariates may be high dimensional, which, in turn, poses statistical challenges for learning personalized decision-making policies. In "Online Decision-Making with High-Dimensional Covariates," H. Bastani and M. Bayati introduce the LASSO Bandit, an adaptive decision-making algorithm that efficiently leverages high-dimensional user covariates by learning sparse models of decision rewards. The authors illustrate the practical relevance of such an approach by evaluating it against a personalized medication dosing problem, finding that the LASSO Bandit outperforms existing bandit methods and physicians in correctly dosing a majority of patients. Big data have enabled decision makers to tailor decisions at the individual level in a variety of domains, such as personalized medicine and online advertising. Doing so involves learning a model of decision rewards conditional on individual-specific covariates. In many practical settings, these covariates are high dimensional; however, typically only a small subset of the observed features are predictive of a decision's success. We formulate this problem as a K-armed contextual bandit with high-dimensional covariates and present a new efficient bandit algorithm based on the LASSO estimator. We prove that our algorithm's cumulative expected regret scales at most polylogarithmically in the covariate dimension d; to the best of our knowledge, this is the first such bound for a contextual bandit. The key step in our analysis is proving a new tail inequality that guarantees the convergence of the LASSO estimator despite the non-i.i.d. data induced by the bandit policy. Furthermore, we illustrate the practical relevance of our algorithm by evaluating it on a simplified version of a medication dosing problem. A patient's optimal medication dosage depends on the patient's genetic profile and medical records; incorrect initial dosage may result in adverse consequences, such as stroke or bleeding. We show that our algorithm outperforms existing bandit methods and physicians in correctly dosing a majority of patients.
