Elicitation of user preferences is an effective way to improve the quality of recommendations, especially when there is little or no user history. In this setting, a recommendation system interacts with the user by asking questions and recording the responses. Various criteria have been proposed for optimizing the sequence of queries in order to improve understanding of user preferences and thereby the quality of downstream recommendations. A compelling approach for preference elicitation is the Expected Value of Information (EVOI), a Bayesian approach which computes the expected gain in user utility for possible queries. Previous work on EVOI has focused on probabilistic models of users for computing posterior utilities. In contrast, in this work we explore model-free variants of EVOI which rely on function approximations in order to avoid strong modeling assumptions. Specifically, we propose to learn a user response model and user utility model from existing data, which is often available in real-world systems, and to use these models in EVOI in place of the probabilistic models. We show promising empirical results on a preference elicitation task using our approach.