본 논문은 (준) 밴딧 피드백을 사용한 다중 클래스 리스트 분류 문제를 연구합니다. 입력 예시는 K개의 가능한 레이블 집합 중 m개 크기의 부분집합으로 매핑됩니다. 각 라운드에서 학습자는 주어진 예시와 연관된 기저 진실 레이블 집합에 있는 예측 레이블로 구성된 피드백을 관찰합니다. 주요 결과는 $(\varepsilon,\delta)$-PAC 변형 문제에 대한 알고리즘을 설계한 것으로, $\widetilde{O} \big( (\mathrm{poly}(K/m) + sm / \varepsilon^2) \log (|H|/\delta) \big)$의 샘플 복잡도를 사용하여 높은 확률로 $\varepsilon$-최적 가설을 반환합니다. 여기서 H는 기저 (유한) 가설 클래스이고 s는 주어진 예시에 대한 진실 레이블 수의 상한입니다. 이 경계는 $s \ll K$일 때 조합적 준-밴딧에 대한 알려진 경계를 개선합니다. 또한, $s = O(1)$인 경우 경계의 주요 항은 해당 완전 정보율과 일치하며, 밴딧 피드백이 본질적으로 비용이 들지 않음을 의미합니다. PAC 학습 알고리즘은 H에 대한 ERM 오라클에 접근할 수 있는 경우 계산적으로 효율적입니다. $s=m=1$에 해당하는 단일 레이블 분류의 특수한 경우에 대해 $O \big((K^7 + 1/\varepsilon^2)\log (|H|/\delta)\big)$의 샘플 복잡도 경계를 증명하는데, 이는 최근 결과(Erez et al. '24)를 개선합니다. 또한, 데이터를 적대적으로 생성할 수 있는 후회 최소화 설정을 고려하고 $\widetilde O(|H| + \sqrt{smT \log |H|})$의 후회 경계를 설정합니다. 본 결과는 단순한 단일 레이블 설정(Erez et al. '24)에서 이전 작업을 일반화하고 확장하며, s-희소 보상을 가진 상황적 조합적 준-밴딧 문제에 더 일반적으로 적용됩니다.
