A major challenge in recommender systems is handling new users, whom are also called $\textit{cold-start}$ users. In this paper, we propose a novel approach for learning an optimal series of questions with which to interview cold-start users for movie recommender systems. We propose learning interview questions using Deep Q Networks to create user profiles to make better recommendations to cold-start users. While our proposed system is trained using a movie recommender system, our Deep Q Network model should generalize across various types of recommender systems.