Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum

Guangjian Zhang, Zhengyi Yang, Xiaoyang Wang

How much does high confidence cost when a multiclass learner sees only whether its prediction is correct? We separate two behaviors in realizable bandit PAC learning. An anchored d…