Adaptive Learning: Algorithms and Complexity