We propose an algorithm that enables robots to improve their spatial-semantic representation of an environment by engaging users in dialog during a guided tour. The algorithm selects the best information gathering actions in the form of targeted questions that reduce the ambiguity over the grounding of user-provided natural language descriptions (e.g., “The kitchen is down the hallway”). These questions include those that query the robot's local surround (e.g., “Are we in front of the kitchen?”) as well as areas distant from the robot (e.g., “Is the lounge near the conference room?”). Our algorithm treats dialog as an optimization problem that seeks to balance the information-theoretic value of candidate questions with a measure of cost associated with dialog. In this manner, the algorithm determines the best questions to ask based upon the expected entropy reduction, while accounting for the burden on the user. We evaluate entropy reduction for a joint distribution over a hybrid metric, topological, and semantic representation of the environment learned from user-provided descriptions and the robot's sensor data during the guided tour. We demonstrate that, by asking deliberate questions of the user, the method significantly improves the accuracy of the learned map.