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.

本文提出了交互式学习的抽象框架 —— 交互估计，其中目标是通过学习者查询的点与其类似性来估计目标。我们介绍了一种称为不相似维度的组合度量，从很大程度上捕获了我们模型中的可学习性。我们提出了一种简单、通用和广泛适用的算法，对其进行了后悔和 PAC 泛化边界的求解，这些边界在新维度中是多项式的。我们展示了我们的框架涵盖并统一了两个经典的学习模型：统计查询学习和结构化强化学习。我们还说明了不相似维度与两种框架的众所周知的参数的关系，在某些情况下得到了显着改进的分析。