연구진은 고정 예산 베스트 암 식별 알고리즘이 정적 오라클의 오류 감소율과 일치할 수 없음을 증명했어요. 정적 오라클은 사전에 모든 암의 평균을 알고 있어 최적의 샘플링 비율을 결정할 수 있습니다.
K가 3 이상이고, 보상이 단일 파라미터 자연 지수족에서 추출될 경우, 어떤 알고리즘에 대해서도 오류 감소율이 정적 오라클보다 최대 (1 + log(K)/8)⁻¹ 배 느린 경우가 존재합니다.
이는 Qin(2022)이 제기한 미해결 질문에 답하며, 고정 예산 베스트 암 식별이 복잡성을 갖지 않음을 시사합니다.