Practical, Provably-Correct Interactive Learning in the Realizable
  Setting: The Power of True Believers
  We consider interactive learning in the realizable setting and develop a
general framework to handle problems ranging from best arm identification to
active classification. We begin our investigation with the observation that
agnostic algorithms \emph{cannot} be minimax-optimal in the realizable setting.
Hence, we design novel computationally efficient algorithms for the realizable
setting that match the minimax lower bound up to logarithmic factors and are
general-purpose, accommodating a wide variety of function classes including
kernel methods, H{\"o}lder smooth functions, and convex functions. The sample
complexities of our algorithms can be quantified in terms of well-known
quantities like the extended teaching dimension and haystack dimension.
However, unlike algorithms based directly on those combinatorial quantities,
our algorithms are computationally efficient. To achieve computational
efficiency, our algorithms sample from the version space using Monte Carlo
"hit-and-run" algorithms instead of maintaining the version space explicitly.
Our approach has two key strengths. First, it is simple, consisting of two
unifying, greedy algorithms. Second, our algorithms have the capability to
seamlessly leverage prior knowledge that is often available and useful in
practice. In addition to our new theoretical results, we demonstrate
empirically that our algorithms are competitive with Gaussian process UCB
methods.
