Mental health patients often undergo a variety of treatments before finding an effective one. Improved prediction of treatment response can shorten the duration of trials. A key challenge of applying predictive modeling to this problem is that often the effectiveness of a treatment regimen remains unknown for several weeks, and therefore immediate feedback signals may not be available for supervised learning. Here we propose a Machine Learning approach to extracting audio-visual features from weekly video interview recordings for predicting the likely outcome of Deep Brain Stimulation (DBS) treatment several weeks in advance. In the absence of immediate treatment-response feedback, we utilize a joint state-estimation and temporal difference learning approach to model both the trajectory of a patient's response and the delayed nature of feedbacks. Our results based on longitudinal recordings from 12 patients with depression show that the learned state values are predictive of the long-term success of DBS treatments. We achieve an area under the receiver operating characteristic curve of 0.88, beating all baseline methods.