We develop a prediction-based prescriptive model for learning optimalpersonalized treatments for patients based on their Electronic Health Records(EHRs). Our approach consists of: (i) predicting future outcomes under eachpossible therapy using a robustified nonlinear model, and (ii) adopting arandomized prescriptive policy determined by the predicted outcomes. We showtheoretical results that guarantee the out-of-sample predictive power of themodel, and prove the optimality of the randomized strategy in terms of theexpected true future outcome. We apply the proposed methodology to developoptimal therapies for patients with type 2 diabetes or hypertension using EHRsfrom a major safety-net hospital in New England, and show that our algorithmleads to a larger reduction of the HbA1c, for diabetics, or systolic bloodpressure, for patients with hypertension, compared to the alternatives. Wedemonstrate that our approach outperforms the standard of care under therobustified nonlinear predictive model.