본 논문은 컨텍스트 기반 조합 반-밴딧 문제를 연구하며, 입력 컨텍스트가 $K$개의 가능한 액션 중 크기 $m$의 부분 집합에 매핑되는 경우를 다룬다. 특히 보상의 합이 $s \ll K$로 제한되는 $s$-희소성을 가정한다. 이 논문은 $(\epsilon,\delta)$-PAC 문제에 대한 알고리즘을 설계하여 $\tilde{O}((poly(K/m)+sm/\epsilon^2) \log(|\Pi|/\delta))$의 샘플 복잡도로 $\epsilon$-최적 정책을 반환한다. 이는 $s \ll K$일 때 기존의 조합 반-밴딧에 대한 경계보다 개선된 것이며, $s=O(1)$일 때는 밴딧 피드백이 사실상 비용이 들지 않는다는 것을 의미한다. 또한, 단일 레이블 분류의 특수한 경우에 대한 개선된 샘플 복잡도 경계를 제시하고, 적대적으로 생성된 데이터에 대한 후회 최소화 설정을 고려하여 후회 경계를 설정한다.
