The objective of the proposed research is to develop systems to facilitate human-machine collaboration by interacting with humans using a variety of relational query types. The work consists of three aims, each focused on a different facet of human-machine collaboration. In the first aim, I develop a framework for jointly learning a human's ideal preference point and a metric under which the human makes preference assessments from paired comparisons. In the second aim, I propose a new query type, develop a framework for learning a metric that governs human similarity perception, and derive theoretical sample complexity bounds. This query was designed to elicit more informative responses, which requires fewer overall interactions with the human to obtain strong performance. In the third aim, I propose a method of leveraging the power of natural language to learn human preferences via paired comparisons. In all, the proposed work takes concrete steps towards more accurate, efficient, and flexible human-machine collaboration.