  We study an abstract framework for interactive learning called interactive
estimation in which the goal is to estimate a target from its "similarity'' to
points queried by the learner. We introduce a combinatorial measure called
dissimilarity dimension which largely captures learnability in our model. We
present a simple, general, and broadly-applicable algorithm, for which we
obtain both regret and PAC generalization bounds that are polynomial in the new
dimension. We show that our framework subsumes and thereby unifies two classic
learning models: statistical-query learning and structured bandits. We also
delineate how the dissimilarity dimension is related to well-known parameters
for both frameworks, in some cases yielding significantly improved analyses.
