Online Decision Making with High-Dimensional Covariates
By Hamsa Bastani, Mohsen Bayati. 2020
433 citations recorded by the source corpus.
Big data has enabled decision-makers to tailor decisions at the individual-level in a variety of domains such as personalized medicine and online advertising. This 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 multi-armed bandit with high-dimensional covariates, and present a new efficient bandit algorithm based on the LASSO estimator. Our regret analysis establishes that our algorithm achieves near-optimal performance in comparison to an oracle that knows all the problem parameters. The key step in our analysis is proving a new oracle 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 real-world clinical problem of warfarin dosing. A patient's optimal warfarin 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 as well as physicians to correctly dose a majority of patients.
Subfields: Artificial Intelligence, Management Science and Operations Research, Game & Decision Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Susan Athey
- Stefan Wager
- Nathan Kallus
- Jack Dunn
- Guido W. Imbens
- Angela Zhou
- Osbert Bastani
- Carolyn Kim
In Management Science and Operations Research
- Susan Athey
- Stefan Wager
- Nathan Kallus
- Guido W. Imbens
- Zhengyuan Zhou
- Maria Dimakopoulou
- Angela Zhou
- Jack Dunn
In Game & Decision Theory
- Carolyn Kim
- Jack Dunn
- Osbert Bastani
- Susan Athey
- Nathan Kallus
- Guido W. Imbens
- Zhengyuan Zhou
- Maria Dimakopoulou
Citations in the corpus
- Machine Learning Methods That Economists Should Know About (2019, methodology): “See Bastani and Bayati [2015] for some discussion. A risk is that if the algorithm estimates a simple linear model mapping characteristics to outcomes, then the algorithm may suggest a great deal of certainty about outcomes for an arm in a region of characteristic space where that treatment arm has ”
- Balanced Linear Contextual Bandits (2018, background): “Several successful contextual bandit designs have been proposed (Auer 2003), (Li et al. 2010), (Agrawal and Goyal 2013), (Agarwal et al. 2014), (Bastani and Bayati 2015).”
- Estimation Considerations in Contextual Bandits (2017, methodology): “Even though in principle a variety of methods can be used to consistently estimate outcome models in the presence of complex, non-uniform arm assignment in large samples (Ridge regression as in [6, 45], ordinary least squares as in [32], LASSO as in [16]), in the early stages of learning where sampl”
- Policy Evaluation and Optimization with Continuous Treatments (2018, background): “Previous work on predicting dosage policies [2, 11] has evaluated accuracy based on prediction of the correct category of dosage, “low” (<21 mg/wk), “medium” (> 21 mg/wk,< 49 mg/wk) or “high” (> 49 mg/wk).”
- Optimal trees for prediction and prescription (2018, background): “The online version of this problem, called the contextual bandit problem, has been studied by several authors [75, 53, 6]) in the multi-armed bandit literature [52].”
- Learning Interpretable Models with Causal Guarantees (2019, positive): “…of an intervention on an individual (called an individual treatment effect )—e.g., the efficacy of a drug on a patient (Consortium, 2009; Kim et al., 2011; Bastani and Bayati, 2015; Henry et al., 2015), whether a defendent in a court case is a flight risk (Kleinberg et al., 2017), or whether an…”
- The Impact of Machine Learning on Economics (2018, methodology): “, 2017), LASSO (Bastani and Bayati, 2015), and random forests (Dimakopoulou et al., 2017; Feraud et al., 2016)). Another choice concerns the heuristic used to balance exploration versus exploitation, with leading choices Thompson Sampling and Upper Confidence Bounds (UCB) Chapelle and Li (2011). Dim”
- Learning to Personalize from Observational Data (2016, methodology): “In each of [11, 12, 13], the proposed solution is to fit m regression functions, and, for a new instance, predict m outcomes and pick the smallest prediction (subject to cleverly ensuring su cient exploration by, e.”
- Optimal Prescriptive Trees (2019, neutral): “The online version of this problem, called the contextual bandit problem, has been studied by several authors (Li et al. 2010, Goldenshluger and Zeevi 2013, Bastani and Bayati 2015) in themultiarmed bandit literature (Gittins 1989).”
- Offline Multi-Action Policy Learning: Generalization and Optimization (2018, background): “…a wide range of domains have gained the ability to target products, services, and information provision based on individual characteristics (Kim et al. (2011), Ozanne et al. (2014), Bertsimas and Kallus (2014), Bastani and Bayati (2015), Kallus and Udell (2016), Athey (2017), Farias and Li (2018)).”