PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
The paper introduces a new combinatorial parameter, the bandit DS dimension (BDS(H)), to sharply characterize sample complexity for multiclass PAC learning under bandit feedback. This dimension aggregates neighbor counts across coordinates, leading to a sample complexity scaling directly with this total neighbor size. It provides tight upper and lower bounds resolving previous multiplicative gaps.