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
