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

Published in Advances in Neural Information Processing Systems (NeurIPS 2026), 2026

We characterize sample complexity up to logarithmic factors through the bandit DS dimension and develop the ListCascade algorithm connecting bandit learning with list learning.

Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri (alphabetical order)
Download Paper