Selecting informative queries is a crucial component of learning and decision-making, where models of information searchhave been widely used to provide normative guidance. Yet a typical requirement of these models is complete informationabout the underlying probabilistic structure of the environment, which is seldom met in real-world situations. Thus,information search models are blind to the epistemic uncertainty that comes with learning through experience, and do notdistinguish between probabilities estimated from a sample of two and a sample of one million. We develop a learningparadigm where a successful strategy needs to balance the exploration of queries with high epistemic uncertainty, with theexploitation of queries already known to be useful. We show that a Bayesian sampling variant of traditional informationsearch models learns faster and performs better, but most surprisingly, that a simple take-the-difference heuristic (TTD)performs competitively using only the absolute difference between observed frequencies.