Characterizing the learnability of interactive learning has posed to be a challenge for the longest time. It was not untill recently that a unifying theory of interactive learning was presented, where it was shown a single quantity is both necessary and sufficient for sample-efficient learning. However, learnability results for this setting rely on overly optimistic assumptions about the hypothesis class and simultaneously are not model-dependent. The focus of this dissertation is to address both these issues. In the first half of the dissertation, we attempt to understand how to adapt the model-independent results to characterize learnability for interactive learning in a way which adapts to the problem instance. Then, in the second half of the dissertation, we first work towards understanding the necessity of the assumption used to prove these learnability results and then try to relax these assumptions and find more practical alternatives that still provide us with similar information and guarantees. The work in this dissertation can be seen as progress in developing theoretical guarantees that have practical implications in algorithm choice and design for interactive learning and classification.