Online Decision Making with High-Dimensional Covariates

Hamsa Bastani () and Mohsen Bayati ()
Additional contact information
Hamsa Bastani: Wharton School, Operations Information and Decisions, University of Pennsylvania, Philadelphia, Pennsylvania 19104
Mohsen Bayati: Stanford Graduate School of Business, Stanford University, Stanford, California 94305

Operations Research, 2020, vol. 68, issue 1, 276-294

Abstract: 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.

Keywords: contextual bandits; adaptive treatment allocation; online learning; high-dimensional statistics; LASSO; personalized decision making (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (25)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1902 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:1:p:276-294

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().