The technology described herein allows an interactive program to leverage a knowledge graph to maximize the likelihood of successfully understanding the user's query and at the same time minimize the number of turns taken to understand the user. A goal of the technology described herein is to formulate response queries that have a probability of completing the user's requested task accurately while issuing the fewest number of response queries to the user before determining the intended task. In order to accomplish this, the technology combines a reinforced learning mechanism with a knowledge-graph simulation score to determine the optimal response query.