This paper details a new methodology, instance-based reinforcement learning, for constructing adaptive treatment strategies from randomized trials. Adaptive treatment strategies are operationalized clinical guidelines which recommend the next best treatment for an individual based on his/her personal characteristics and response to earlier treatments. The instance-based reinforcement learning methodology comes from the computer science literature, where it was developed to optimize sequences of actions in an evolving, time varying system. When applied in the context of treatment design, this method provides the means to evaluate both the therapeutic and diagnostic effects of treatments in constructing an adaptive treatment strategy. The methodology is illustrated with data from the STAR*D trial, a multi-step randomized study of treatment alternatives for individuals with treatment-resistant major depressive disorder.