PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

Steve Hanneke, Qinglin Meng, Shay Moran +1

We study the problem of multiclass PAC learning with bandit feedback in the realizable setting. In this framework, there is an unknown data distribution over an instance space $\ma…