Chronic depression is one of the leading causes for disability and severely impacts quality of life in US adults. As the disease can progress uniquely from patient-to-patient, clinical guidelines should not be one-size-fits-all for every patient. This heterogeneity highlights a need for the development of treatment selection algorithms that leverage person-level data and account for uncertainty in patient treatment response. We formulate the treatment selection problem for patients with chronic depression as a Markov Decision Process with the objective of finding the optimal treatment policy. Patients are categorized by their disease progression patterns and are assumed to have a latent treatment response type, i.e., responding the best to one of the available treatments. To create personalized treatment plans, we propose 1) a model-based approach that requires foreknowledge of the natural history disease model, 2) a model-free approach – Fitted-Q Iteration that relies only on patient observations, and they are investigated as alternatives to 3) a rule-based policy based on expert experience and clinical guidelines. Using simulated patient trajectories, we evaluate their policy performance under metrics such as health outcomes and accuracy in identifying a patient’s latent treatment response type. Our results show that the model-based algorithm provides the best policy with the highest health outcomes and accuracy in identifying the most effective treatment to each patient. It is also robust to changes in health utility, treatment disutility and probability of treatment discontinuation.